Comparing different sorting algorithms for time performance has always been amusing. It has been done tons of time. But you should try it out for yourself. 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 (using 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 for real.
- 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. 😀

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.

Nice article Sir

Sir i wanted to know how can we precisely calculate time in bubble sort and selection sort for 10 integers?

Any sorting algorithm for 10 integers will take negligible time. You won’t gain anything by measuring it.

Actually Bubble Sort is the fastest if the data set is already sorted. This actually occurs. If you maintain a data set and add a few records here and there, it is faster. If you don’t know anything about your data set you might want to use a mid-level performer. If you know that it is random, sure, quicksort is the best choice.

No, Insertion sort is fastest for sorted data. Try running bubble sort on 1 Million sorted integers. And then insertion sort on the same data set.

Bubble sort is always O(n^2). To see this notice the condition of both the `for` loops in bubble sort.

Insertion sort however reduces to O(n) if the data is sorted. Check the loop condition for insertion sort in the code.

Sir is this possible is I have 6 number only? coz in out study we only have to sort 6 numbers…I always get 0 when I measure their time….. I really need to know 😦

plz upload an other sorting articles

Hi, I see that you are using the global variable “list” for storing and sorting the numbers. That way, once the bubblesort function is called, the array is already sorted. Naturally, when the insertion sort and quicksort are called after that, the functions are actually running on sorted data(that has been sorted by the bubblesort function).

So for every loop in the main function, only bubblesort is actually sorting the input.

Please check.

Hi Ravina,

Take a look at the loop in which sorting functions are called. Prior to invoking sort function, I have called “read();” function, which reads integers from a file containing random integers and adds it to “list”. So it is guaranteed that each sorting function has same input array.

Thank you for your code. It really helped me a lot. But I tried adding heap sort and merge sort but it doesn’t work. Do you know how it was done?

Is the quick sort result an april first’s joke?

My results are for 1000: 1.453 , for 5000: 7.235, for 10000: 14.435, for the next one the program stopped and returned -1073741571 instead of 0… Help ASAP please

This result is totally unexpected. Please verify if you are indeed running quick sort.

I changed the array size to 3000 so the value for each case was:

case 100 :

length = 500;

break;

case 500 :

length = 1000;

break;

case 1000 :

length = 1500;

break;

case 1500 :

length = 2000;

break;

case 2000 :

length = 2500;

break;

case 2500 :

length = 3000;

break;

case 3000 :

length = 3001;

break;

And when I ran it, the quick sort’s time was 1000=0.384615, 1500=0.549451, 2000=0714286, 2500=0.879121, 3000=1.098901 and these times were larger than the bubble sort which isn’t supposed to. What could be the problem?

I checked , but it ended up with another problem. I fixed it though 😀 So everything’s ok now and I hope you all have a nice day 🙂

I would like to ask how did you fix the problem for the quick sort because I’m having the same problem. Thank you.

Well seems that you need that file from which the numbers are read.. I didn’t read the whole article and just went with copy-pasting the code. I later solved the problem using rand() , srand(time(0)), and that way I allways got new items for sorting, I guess you could google those functions

Oh, I just saw that actually even that is mentioned in the article.. So maybe you had the same problem?

Yeah. I’m having the same problem. Can you show me the code, if you don’t mind sharing it? I really need to know how will it get fixed. Thank you.

Is anyone else getting a Segmentation fault for quick sort? i changed the lengths to 1………to a 1000000.