Comparasion Time Complexity of Insertion Sort

Question

I've implemented insertion sort in C(Visual Studio) and Java(Eclipse) to analyse the time required for completion and to compare the difference in both the languages.

I tried to find out the worst case time required for the algorithm to complement.(Convert decreasing array to increasing one).

I run my code with samples of 10,000, 50,000 and 100,000 entries and the following were the observations:

In C:
10000: 0.172 seconds
50000: 3.874 seconds
100000: 15.384 seconds

whereas in Java
10000: 0.048 seconds
50000: 0.385 seconds
100000: 1.924 seconds

My code is normal insertion sort code. Nothing new in it. The time measured are only of insertion sort code and i/o operations are independent of it. e.g:

Input
Timer starts here
Insertion Sort
Timer ends
Summary(Time required and all)

I believed C was faster than Java but I couldn't justify this result..

EDIT: Here's the C code

void InsertionSort(int a[]) {
    int i;
    clock_t st, end;
    st = clock();
    for (i = 1; i < MAX; i++)   {
        int temp = a[i];
        int pos = i - 1;
        while(a[pos] > temp)    {
            a[pos + 1] = a[pos];
            pos--;
        }
        a[pos + 1] = temp;
    }
    end = clock();
    printf("\nSorting Completed. Time taken:%f", (double)(end - st) / CLOCKS_PER_SEC);
}

and Java Code:

public void Sort(int a[], int size) {
        int i;
        for (i = 1; i < size; i++)  {
            int temp = a[i];
            int pos = i - 1;
            while(pos >= 0 && a[pos] > temp)    {
                a[pos + 1] = a[pos];
                pos--;
            }

            a[pos + 1] = temp;
        }
}

Exactly, use -O3 flag for compilation, and make sure you are in Release mode. — Vlad Krasnov, Jun 11 '13 at 07:47
@bugsbunny Okay, compile your code with the -O3 flag and compare the speeds again :) — Nobilis, Jun 11 '13 at 07:50
If that doesn't work try including your insertion sort and setup code in the question. — selig, Jun 11 '13 at 07:51
It's probably because depending on the Array and the items, Java chooses the most efficient way to sort them, whereas C may be more straightforward. — Fabinout, Jun 11 '13 at 07:51
Note in Visual Studio, this will be the `/O3` flag, I believe. But there should be an "optimizations" setting in one of the build config tabs to control this. — Oliver Charlesworth, Jun 11 '13 at 07:53
@Fabinout - I was under the impression the OP has implemented insertion sort themselves. — selig, Jun 11 '13 at 08:00
Have you can tried running the insertion sort function multiple time on same data set instead of running just once. I would suggest run multiple times on same data set to get average run time. — praks411, Jun 11 '13 at 08:09
@praks411: Run-to-run discrepancies are unlikely to explain a 10-to-1 speed difference... — Oliver Charlesworth, Jun 11 '13 at 08:10
Is it possible your C-program compiled with Visual Studio also is compiled towards the MSIL http://en.wikipedia.org/wiki/Common_Intermediate_Language If that is the case, you are comparing two implementations of virtual machines (Java virtual machine versus MSIL virtual machine) — Peter DW, Jun 11 '13 at 08:29
Try to compile\run both codes on the Terminal instead of using IDE — Khaled.K, Jun 11 '13 at 08:50
@OliCharlesworth I altered the project properties and the program runs 4 times faster but still it is slow as compared to Java. Does by any chance JVM implements program in threads even if they are not implemented in program? — SureshS, Jun 11 '13 at 08:53
@bugsbunny, why are you using `clock`? Did you try to profile the code? — Nobilis, Jun 11 '13 at 09:19
@Nobilis I used clock to measure the time taken for the sorting process. I didn't try profiling. — SureshS, Jun 11 '13 at 09:24
@bugsbunny Well, profile the code and compare the times :) After a quick google search there seems to be a profiler available for Visual Studio (if that's what you're using). Consider this link - http://msdn.microsoft.com/en-us/library/ms182372.aspx Other SO posters can weigh in if using clock is an effective way to profile the code but for C on Linux profiling is typically done using `gprof` — Nobilis, Jun 11 '13 at 09:28
@bugsbunny Also consider this link - http://stackoverflow.com/questions/2055685/performance-profiling-measurement-in-c — Nobilis, Jun 11 '13 at 09:35
In VS, are you compiling release or debug? Also, how are you measuring the time in java? — msshapira, Jun 11 '13 at 10:10

Nobilis · Answer 1 · 2013-06-11T12:44:03.377

0

I couldn't get jconsole to print the time so I used the crudest way to compare times (I used your insertion sort implementation) on Linux.

C (gcc is alised to gcc -Wall -Wextra -Wunreachable-code -Waggregate-return -Wshadow):

$ gcc -O3 insertion_sort.c 
$ date; ./a.out; date
Tue Jun 11 20:16:24 MYT 2013
Tue Jun 11 20:16:36 MYT 2013

Java:

$ javac Main.java
$ date; java Main; date
Tue Jun 11 20:19:11 MYT 2013
Tue Jun 11 20:19:32 MYT 2013

It's pretty evident that C outperforms Java, I used an array of size 150 000 and sorted in reverse. I've provided links to my code:

C

Java

My recommendation is to set up a virtual machine running a Linux OS and to try it yourself (learning some Linux is incredibly useful not to mention that C programming is a breeze on it).

edited Jun 11 '13 at 12:44

answered Jun 11 '13 at 12:29

Nobilis

7,310
1
33
67

Ya I've got VMware and I tried it on Linux. C outperforms Java. Now I'm trying the profiler tool in Visual Studio. Still trying optimize code in VS. Thanks for the help. It was very useful.:) – SureshS Jun 11 '13 at 15:39
No problem, I'm very surprised VS would compile C in such a manner, though -O3 makes a huge difference, without it, it took around 48 secs on my machine. – Nobilis Jun 11 '13 at 15:58

Comparasion Time Complexity of Insertion Sort

1 Answers1