Comparing different sorting algorithms for time performance has always been amusing. It has been done tons of time. But you should do it for yourself for your amusement and impressing fellows. Apart from fun, this comparison is very useful in real life. Companies and organisations need to sort and search data all the time. Thus it makes sense to compare and find the best suitable sorting method.

First let me show you the result in a neat graph (courtesy MS Excel charts), displaying **time** (on y-axis) v/s **list size** (on x-axis).

If you are done analysing the graph, please note following points

- The x-axis represents the number of elements sorted.
- The x-axis is not linear (nor logarithmic). Its random, you see 1,000 then 5,000 then 10,000 and so on up to 3,00,000. The last three entries are linear however, and shows the highlight feature of the graph. The difference in the three algorithms performance.
- Quick Sort seems to not want to let go off the axis. It is not a mistake, it is a reality. A sweet reality.
- Bubble sort’s curve would make a dream come true graph for a company’s profit.

Here I reproduce the result in tabular form -

Length | Bubble Sort | Insertion Sort | Quick Sort |

1000 | 0 | 0 | 0 |

5000 | 0.145 | 0.045 | 0 |

10000 | 0.6 | 0.18 | 0 |

50000 | 14.05 | 4.25 | 0.01 |

100000 | 56.9 | 17.62 | 0.02 |

200000 | 229.44 | 69.12 | 0.05 |

300000 | 513.34 | 154.22 | 0.065 |

### Variations in numbers (time recorded)

Consider Insertion Sort’s time taken for 5000 integers, 0.045 seconds. This is an average value. Due to other processes going on at the same time as comparison, the recorded time varies during each run. It also varies from computer to computer (mine one is a decent one though, Intel i3 with 4 GB of RAM). Like in one execution, above time was recorded as 0.04 sec and in other it was 0.05 sec. Same goes for all the time values. In effect I have averaged the time taken in the 4 executions. For greater accuracy keep the number of samples to a minimum 10 (although I leave it to you). And also the code should be executed on a variety of computers and Operating Systems (again I leave that for you). However the differences are so pronounced that a variation of 5-10% does not affect the end result.

### The big question?

You must wonder why I chose the above three algorithms for comparison. Why not merge sort (arguably the fastest sorting algorithm), or heap sort? And pray, why include Bubble Sort at all??

For one the beginners should know that their favourite sorting (Bubble sort), is umm, well, pathetic and un-acceptable. Second, that quick sort is indeed quick. And I had to take some medium performing algorithm, so Insertion Sort was chosen. All three of them are quite popular and easy to understand.

Give me the code

Yeah sure, here it is:

#include <iostream> #include <fstream> #include <cstdlib> #include <ctime> using namespace std; long length = 1000; const long max_length = 300000; int list[max_length]; void read() { ifstream fin("random.dat", ios::binary); for (long i = 0; i < length; i++) { fin.read((char*)&list[i], sizeof(int)); } fin.close(); } void bubbleSort() { int temp; for(long i = 0; i < length; i++) { for(long j = 0; j < length-i-1; j++) { if (list[j] > list[j+1]) { temp = list[j]; list[j] = list[j+1]; list[j+1] = temp; } } } } void insertionSort() { int temp; for(long i = 1; i < length; i++) { temp = list[i]; long j; for(j = i-1; j >= 0 && list[j] > temp; j--) { list[j+1] = list[j]; } list[j+1] = temp; } } long partition(long left, long right) { int pivot_element = list[left]; int lb = left, ub = right; int temp; while (left < right) { while(list[left] <= pivot_element) left++; while(list[right] > pivot_element) right--; if (left < right) { temp = list[left]; list[left] = list[right]; list[right] = temp; } } list[lb] = list[right]; list[right] = pivot_element; return right; } void quickSort(long left, long right) { if (left < right) { long pivot = partition(left, right); quickSort(left, pivot-1); quickSort(pivot+1, right); } } int main() { double t1, t2; for (length = 1000; length <= max_length; ) { cout << "\nLength\t: " << length << '\n'; read(); t1 = clock(); bubbleSort(); t2 = clock(); cout << "Bubble Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n"; read(); t1 = clock(); insertionSort(); t2 = clock(); cout << "Insertion Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n"; read(); t1 = clock(); quickSort(0, length - 1); t2 = clock(); cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n"; switch (length) { case 1000 : length = 5000; break; case 5000 : length = 10000; break; case 10000 : length = 50000; break; case 50000 : length = 100000; break; case 100000 : length = 200000; break; case 200000 : length = 300000; break; case 300000 : length = 300001; break; } } return 0; }

I encourage you to copy the code (modify it to suit your needs), compile it with your choice of compiler and execute it. And share the results with us. I will be glad to showcase here what you found (and how fast your computer runs )

IMPORTANT : The above code requires a file ‘**random.dat**‘ which contains 3,00,000 integers stored randomly. This file is read each time before a sorting is performed. You can download it here http://www.box.net/shared/1n3r3hedv86351iun6f5 or here https://skydrive.live.com/?cid=a976bcd81e2434ba&sc=documents&id=A976BCD81E2434BA%21114# The file is 1.14MB sized.

Alternatively you can generate ‘**random.dat**‘ file through this code. This way you can generate a bigger file for more numbers.

#include <fstream> #include <cstdlib> #include <ctime> using namespace std; const size_t length = 300000; int main() { ofstream fout("random.dat", ios::binary); srand(time(NULL)); int r; for (size_t i = 0; i < length; i++) { r = rand(); fout.write((char*)&r, sizeof(r)); } fout.close(); return 0; }

Also you can download both the codes, there executables and random.dat in this RAR file(1.01 MB) http://www.box.net/shared/31ofn1v53qrdm0y2cdce or here https://skydrive.live.com/?cid=a976bcd81e2434ba&sc=documents&uc=1&id=A976BCD81E2434BA%21116#

WARNING : The total execution time can exceed 20 minutes (or even more) on slow processors. It may seem that program is hung after sorting 50,000 numbers, but it is not so. The screen stops responding because, the bubble sort starts taking longer times (in several minutes). So nothing to worry, just watch a video or two on vimeo (or youtube).

### Conclusion

I would conclude this, that

- Bubble Sort is not suitable in any circumstance. It is an O(n
^{2}) algorithm with a large constant. In simple words, time required to perform bubble sort on ‘n’ numbers increases as square of ‘n’. Thus it is quite slow. - Insertion Sort is suitable for small files, but again it is an O(n
^{2}) algorithm, but with a small constant. Also note that it works best when the file(/numbers) is already almost sorted. - Quick Sort amazed me. Didn’t you get amazed?! Well it is an O(n*log(n)) algorithm on an average case and an O(n
^{2}) algorithm in the worst case scenario. (Quick sort’s worst case occurs when the numbers are already sorted!!) The graph speaks it all. You need this algorithm when the list is large and time is premium.

Have a nice time comparing!

Hi, like your programme. But are you sure that quick sort sorts the WHOLE list properly? It seems like not.. maybe it should write the sorted file for comparison? Possibly some flaw in the techniques.. Just suggestion.

Operating System

MS Windows Vista Business 32-bit SP2

CPU

Intel Core 2 Duo E8400 @ 3.00GHz 44 °C

Wolfdale 45nm Technology

RAM

4.00 GB Dual-Channel DDR2 @ 399MHz (6-6-6-18)

Motherboard

Hewlett-Packard 2820h (XU1 PROCESSOR) 36 °C

Hard Drives

244GB Seagate ST3250310AS ATA Device (SATA) 33 °C

I did not do anything while it was sorting. Processor was jumping 40-80%

Length : 1000

Bubble Sort : 0.004 sec

Insertion Sort : 0.001 sec

Quick Sort : 0.002 sec

Length : 5000

Bubble Sort : 0.117 sec

Insertion Sort : 0.034 sec

Quick Sort : 0.002 sec

Length : 10000

Bubble Sort : 0.471 sec

Insertion Sort : 0.132 sec

Quick Sort : 0.002 sec

Length : 50000

Bubble Sort : 11.846 sec

Insertion Sort : 3.248 sec

Quick Sort : 0.012 sec

Length : 100000

Bubble Sort : 47.114 sec

Insertion Sort : 13.052 sec

Quick Sort : 0.024 sec

Length : 200000

Bubble Sort : 189.192 sec

Insertion Sort : 52.212 sec

Quick Sort : 0.046 sec

Length : 300000

Bubble Sort : 437.146 sec

Insertion Sort : 117.487 sec

Quick Sort : 0.07 sec

By these results- i really think there the quick sort can be incorrect.

@Peter : Thanks for sharing your results (in fact lots of details :) ). Although i had printed a subset of sorted values after each sort. On your suggestion i actually added code to print the sorted result in a file. Although there are lot of values to check, I checked manually the output, and it is well Correct!. So I guess quick sort surprised you, didn’t it. :D

Can someone give the results of time comparison to execute these three algorithms for 1million random numbers. I tried it in java but my console is not showing all 1 million numbers on the screen.

Also please let me know how we can calculate the exact time.. Can we have a timer inside the code that records the execution time? or do we have to calculate it manually?

I would appreciate if i can have a java code to put up a timer inside the program for execution…so that the results would be accurate..

Please help me..

Console cannot show 1 million numbers. So instead of printing to console (like using System.out.println), print the numbers to a file, which you can read in a text editor. Or you can print to console only, but redirect the standard output to a text file.

This is done by “java comparison > out.txt” while executing.

I am not sure about timing in Java, but this should work->

I tried to add Merge sort to the comparison, but it didn’t work…can you show how to modify it, please?

how was merge sort done with comparison ?

sir, thanks for the article ! :)

Thanks a lot for the code, but I have one suggestion.

I was using your code to count the number of comparisons made by the quicksort and I believe I’ve found a mistake, that don’t compromise the sorting, but the efficiency.

In the line 63, while(list[left] <= pivot_element), I had to add the comparison (left < right), leading to while( (left < right) && list[left] <= pivot_element). Without this comparison, during some runs the comparisons were being made between the pivot and an element outside the list limit. As I'm a beginner, a test with a 5-element list was very productive. ;-)

This means that, in the average, quicksort should be even faster.

Best regards.

Luciana.

Thanks 4 coding sir….I’m a new learner so can u provide me coding in c for comparison in complexity of quick, merge and bubble sort

Thanks 4 coding sir, am very great-full …. plz can u provide me coding for comparison in complexity of insertion sort and merge sort only. am a new learner (answer in c++ plz)

Nice research work. I think it would be more interesting to compare quick sort with merge sort to check how 2 average time O(nlogn) do.

Also is the data for the numbers generated randomly? How about different trends to fit in with insertion sort?

Was searching for valid comparison on the net and arrived on your page…

Your test has a LOT of flaws.

1/ What is your timer resolution ?

2/ What kind of data do you use ? Random ? Nearly sorted ? Inversed ? Each of those impact hugely the outcome of the performance of the sort.

3/ Load (or copy) the same data in memory like 100x time, so you wont include the loading time and then measure the TOTAL time for 100 sets ONCE.

Then divide your total time by 100. You need to average the time for each run. There is no way your benchmark can be accurate given the current measurement system.

Finding 0 for a quicksort of 5000 items, just doesn’t make any sense at all. It is most likely than the CPU takes at least a few 100k cycles. Most likely it takes probably around 0.1ms or 0.2ms for your sort.