## Java Program - Performance of Sorting Algorithms

• 17th Aug, 2019
• 17:23 PM

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.

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

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

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.