- 17th Aug 2019
- 04:53 am
There are various sorting algorithms in the field of computer science. Each of them performs different in different scenerio. In this project we have analysed the perfomance of some commonly used sorting algorithms like insertion sort, heap sort, quick sort, merge sort. The sample data size is taken as large as one million integers to see how each algorithms work.
Task 1
In our first task we have modified the quicksort and mergesort such that if data size is below 1000 we use insertion sort and return. These modified versions are called mergesort2 and quicksort2. Let’s see how they compete with quicksort and mergesort. Let’s simulate and tabulate the time taken by each algorithms as follows. Simulated 10 times each time producing 1000000 random keys.
Time Taken for sorting 1000000 random keys by four different algorithms is listed below(in microseconds)
Test No. mergesort mergesort2 quicksort quicksort2
-----------------------------------------------------------------------------------------
1 216.000000 309.000000 286.000000 299.000000
2 199.000000 280.000000 158.000000 228.000000
3 200.000000 277.000000 157.000000 204.000000
4 199.000000 287.000000 158.000000 204.000000
5 200.000000 295.000000 158.000000 205.000000
6 200.000000 288.000000 159.000000 204.000000
7 200.000000 287.000000 157.000000 202.000000
8 201.000000 288.000000 158.000000 203.000000
9 201.000000 287.000000 158.000000 205.000000
10 199.000000 287.000000 158.000000 202.000000
Observation : Clearly mergesort and quicksort outsmarts their modified version
Task 2
In this task we modifiy the quicksort and quicksort2 such that if the data in current range are already sorted we don’t need to break the problem further. Let’s call the modifications as quicksort3 and quicksort4 respectively. Similar to task 1 we simulate for 10 times each time producing 1000000 keys. But inputs are varied as random, sorted and reverse sorted as below
Time Taken for sorting 1000000 random keys by four different algorithms is listed below(in microseconds)
Test No. quicksort quicksort2 quicksort3 quicksort4
-----------------------------------------------------------------------------------------
1 191.000000 256.000000 230.000000 326.000000
2 155.000000 205.000000 162.000000 234.000000
3 155.000000 202.000000 158.000000 203.000000
4 155.000000 203.000000 158.000000 230.000000
5 156.000000 203.000000 159.000000 201.000000
6 154.000000 202.000000 160.000000 201.000000
7 155.000000 203.000000 158.000000 201.000000
8 157.000000 204.000000 160.000000 202.000000
9 155.000000 202.000000 158.000000 201.000000
10 154.000000 201.000000 158.000000 200.000000
Time Taken for sorting 1000000 sorted keys by four different algorithms is listed below(in microseconds)
Test No. quicksort quicksort2 quicksort3 quicksort4
-----------------------------------------------------------------------------------------
1 22.000000 15.000000 1.000000 1.000000
2 21.000000 14.000000 1.000000 0.000000
3 21.000000 14.000000 1.000000 0.000000
4 22.000000 15.000000 0.000000 0.000000
5 21.000000 15.000000 1.000000 1.000000
6 22.000000 14.000000 1.000000 1.000000
7 21.000000 15.000000 0.000000 0.000000
8 22.000000 14.000000 1.000000 1.000000
9 22.000000 15.000000 0.000000 1.000000
10 21.000000 15.000000 0.000000 1.000000
Time Taken for sorting 1000000 reverse sorted keys by four different algorithms is listed below(in microseconds)
Test No. quicksort quicksort2 quicksort3 quicksort4
-----------------------------------------------------------------------------------------
1 23.000000 15.000000 3.000000 3.000000
2 22.000000 15.000000 3.000000 3.000000
3 24.000000 15.000000 3.000000 3.000000
4 24.000000 15.000000 3.000000 3.000000
5 24.000000 16.000000 3.000000 3.000000
6 23.000000 16.000000 3.000000 2.000000
7 23.000000 15.000000 2.000000 3.000000
8 22.000000 16.000000 3.000000 3.000000
9 23.000000 15.000000 3.000000 3.000000
10 23.000000 15.000000 2.000000 2.000000
observation: For random keys all the four algorihms performed equally well. But quicksort3 and quicksort4 were really fast when input keys were already sorted OR reverse-sorted
Task 3
In this third task we make use of the fastest algorithm from task 2 which is quicksort3. This quicksort3 is used as base for implementing quicksort5 and quicksort6. Also quicksort5 uses the pivot to be the median of low, middle, high. Quicksort6 uses 9 equally spreaded keys first. Groups them into three and finds three medians. It further finds median of three medians as pivot. Let’s compare five algorithms as tabulated below. To overcome stack overflow data size is reduced to 100000 which still gives us plenty information for comparing algorithms.
Time Taken for sorting 100000 random keys by five different algorithms is listed below(in microseconds)
Test No. heapsort quicksort quicksort5 quicksort6 quicksort3
--------------------------------------------------------------------------------------------------------------
1 37.000000 61.000000 86.000000 26.000000 79.000000
2 28.000000 17.000000 17.000000 21.000000 14.000000
3 31.000000 13.000000 16.000000 20.000000 13.000000
4 22.000000 13.000000 15.000000 16.000000 14.000000
5 22.000000 14.000000 16.000000 16.000000 14.000000
6 21.000000 13.000000 15.000000 16.000000 14.000000
7 22.000000 13.000000 16.000000 17.000000 14.000000
8 22.000000 13.000000 16.000000 16.000000 14.000000
9 22.000000 13.000000 17.000000 17.000000 14.000000
10 22.000000 13.000000 16.000000 17.000000 13.000000
Time Taken for sorting 100000 sorted keys by five different algorithms is listed below(in microseconds)
Test No. heapsort quicksort quicksort5 quicksort6 quicksort3
--------------------------------------------------------------------------------------------------------------
1 14.000000 2.000000 0.000000 0.000000 0.000000
2 15.000000 2.000000 0.000000 0.000000 0.000000
3 14.000000 2.000000 0.000000 0.000000 0.000000
4 15.000000 2.000000 0.000000 0.000000 0.000000
5 14.000000 2.000000 0.000000 0.000000 0.000000
6 14.000000 2.000000 1.000000 0.000000 0.000000
7 15.000000 2.000000 0.000000 0.000000 0.000000
8 14.000000 2.000000 0.000000 0.000000 0.000000
9 15.000000 2.000000 0.000000 0.000000 0.000000
10 14.000000 2.000000 0.000000 0.000000 0.000000
Time Taken for sorting 100000 reverse sorted keys by five different algorithms is listed below(in microseconds)
Test No. heapsort quicksort quicksort5 quicksort6 quicksort3
--------------------------------------------------------------------------------------------------------------
1 14.000000 2.000000 0.000000 0.000000 0.000000
2 16.000000 3.000000 0.000000 0.000000 0.000000
3 24.000000 2.000000 0.000000 1.000000 1.000000
4 15.000000 2.000000 0.000000 0.000000 0.000000
5 24.000000 4.000000 1.000000 1.000000 0.000000
6 14.000000 3.000000 0.000000 1.000000 1.000000
7 14.000000 2.000000 0.000000 1.000000 0.000000
8 14.000000 2.000000 0.000000 1.000000 0.000000
9 14.000000 2.000000 0.000000 1.000000 0.000000
10 14.000000 2.000000 0.000000 1.000000 0.000000
Time Taken for sorting 100000 orgran-shaped inputs by five different algorithms is listed below(in microseconds)
Test No. heapsort quicksort quicksort5 quicksort6 quicksort3
--------------------------------------------------------------------------------------------------------------
1 15.000000 74.000000 13.000000 12.000000 88.000000
2 15.000000 74.000000 12.000000 11.000000 94.000000
3 16.000000 74.000000 12.000000 12.000000 88.000000
4 15.000000 74.000000 12.000000 11.000000 88.000000
5 15.000000 74.000000 13.000000 12.000000 88.000000
6 15.000000 73.000000 13.000000 12.000000 92.000000
7 15.000000 73.000000 12.000000 12.000000 90.000000
8 16.000000 74.000000 12.000000 11.000000 87.000000
9 15.000000 73.000000 12.000000 11.000000 88.000000
10 15.000000 73.000000 13.000000 12.000000 88.000000
Observation: Quicksort is really fast in all the cases above. Modified quicksort5 and quicksort6 are equally fast. Even in case of reverse-sorted array all versions of quicksort outshines heapsort.
