Time Comparison of Quick Sort, Insertion Sort and Bubble Sort

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).

comparison

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. Winking smile

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 Smile)

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(n2) 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(n2) 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(n2) 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!

About these ads
This entry was posted in Algorithm, Programming and tagged , , , , , , . Bookmark the permalink.

12 Responses to Time Comparison of Quick Sort, Insertion Sort and Bubble Sort

  1. 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.

  2. vinayakgarg says:

    @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

  3. Sravan says:

    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..

    • vinayakgarg says:

      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->

      long start_time = System.nanoTime();
      comparison_method();
      long end_time = System.nanoTime();
      
      long duration = end_time - start_time;
      
  4. John says:

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

  5. L says:

    sir, thanks for the article ! :)

  6. 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.

  7. shubhra singh says:

    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

  8. olatunde yusuf says:

    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)

  9. hitman4life says:

    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?

  10. YeahRight says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s