Skip to content

Assignment 4 Sorting Algorithms

Jump to bottom
shanmuga sudan edited this page Aug 2, 2017 · 2 revisions

  • Strategy Design Pattern:
    Declare a behavior as Interface and dynamically decide the behavior based on user requirement. Here, I create an interface sortable that is implemented by all the algorithms I have taken up for consideration.

  • Steps Performed for the Assignment 4:

  1. Created My Sort class through which the sorting algorithms are called.
  2. Created an interface sortable that holds signature of sort methods.
  3. Created different classes one each for a sorting algorithm and implemented sortable interface.
  4. Created an array to load input size ranging from 10,000 to 1,000,000.
  5. Created an array every time with a input range.
  6. Created a function to perform knuth shuffle on the created array.
  7. Created a function to generate random numbers for the given count.
  8. Created a method that calls every algorithm for the newly created input array.
  • Scenarios considered:
  1. Created a partially sorted array by performing Knuth Shuffle.
    Yates_shuffle#Implementation_errors (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Implementation_errors)This link helped me understand the nuances in Knuth shuffle.
    profiling-sorting-algorithms-against-partially-sorted-data(http://stackoverflow.com/questions/5113158/profiling-sorting-algorithms-against-partially-sorted-data)
  2. Created a random array by using random function in java.
  3. Created an ascending sorted array using Arrays.sort() method in java.
  • Algorithms Considered:
  1. Quick Sort
  2. Merge Sort
  3. Insertion Sort
  4. Selection Sort
  5. Heap Sort
  6. Intro Sort (a hybrid sorting algorithm for efficient sorting)
  • Intro Sort: Intro sort is a hybrid sorting algorithm that combines heap sort and quick sort. I have done a detailed analysis on sorting algorithms and came across the below links which were really helpful. Introsort- wikisource(https://en.wikipedia.org/wiki/Introsort)
    Hybrid_algorithm-wiki_source(https://en.wikipedia.org/wiki/Hybrid_algorithm)
    It begins with quick sort and switches to heap sort once the recursion depth exceeds logarithm of elements sorted. The best, average, worst case run time for this sort is n log n where n is the number of inputs.
    I also did a brief research on TimSort that was adapted to Java SE 7 from Python 2.3. I figured out that Arrays.sort uses Timsort for sorting elements of reference type.

is-java-7-using-tim-sort-for-the-method-arrays-sort ?(http://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort)

  • Run time Analysis:

I spreadsheet provides the runtime analysis of all the sorting algorithms considered

Quick Sort:

Input Size Time in ms (Partially Sorted) Time in ms Random Time in ms Sorted
10000 0 0 0
20000 0 0 0
30000 0 1 0
40000 0 1 0
50000 3 2 0
60000 1 1 0
70000 1 2 0
80000 1 1 0
90000 4 3 0
100000 3 3 2
110000 2 3 1
120000 3 3 1
130000 4 4 1
140000 4 5 1
150000 5 5 2
160000 5 5 2
170000 6 4 1
180000 9 7 2
190000 11 6 1
200000 6 5 2
210000 7 7 3
220000 7 8 3
230000 7 7 3
240000 9 9 4
250000 9 9 4
260000 12 8 5
270000 10 10 5
280000 11 8 4
290000 12 9 3
300000 10 10 4
310000 10 11 4
320000 10 11 6
330000 11 11 7
340000 11 13 8
350000 11 14 8
360000 12 12 8
370000 12 12 9
380000 13 14 10
390000 17 11 8
400000 26 12 9
410000 28 13 7
420000 29 14 10
430000 30 16 11
440000 29 17 12
450000 29 18 13
460000 33 15 12
470000 35 19 13
480000 34 19 14
490000 30 21 15
500000 33 24 16
510000 36 26 14
520000 31 28 13
530000 35 24 15
540000 35 25 16
550000 33 26 17
560000 37 28 18
570000 38 27 15
580000 35 24 15
590000 33 26 15
600000 34 28 14
610000 42 30 16
620000 39 30 14
630000 37 31 18
640000 40 28 14
650000 36 32 18
660000 36 36 16
670000 40 30 16
680000 33 34 17
690000 44 35 18
700000 46 32 15
710000 40 31 16
720000 46 30 17
730000 41 32 18
740000 36 35 17
750000 41 34 16
760000 46 33 18
770000 46 35 17
780000 39 36 18
790000 41 31 20
800000 46 32 21
810000 43 32 22
820000 42 35 21
830000 45 36 22
840000 50 34 22
850000 44 35 22
860000 42 35 22
870000 44 36 22
880000 47 37 22
890000 49 39 22
900000 54 38 21
910000 46 35 22
920000 51 36 23
930000 53 36 22
940000 48 37 22
950000 57 38 22
960000 54 40 21
970000 58 38 24
980000 56 40 22
990000 58 42 22
1000000 59 40 25

Merge Sort:

Input Size Time in ms (Partially Sorted) Time in ms Random Time in ms Sorted
10000 1 1 0
20000 0 1 0
30000 0 0 0
40000 1 2 0
50000 1 3 2
60000 1 4 3
70000 2 3 1
80000 2 5 3
90000 2 4 3
100000 5 6 4
110000 3 8 5
120000 4 7 5
130000 7 8 6
140000 6 9 7
150000 5 7 8
160000 6 8 7
170000 9 7 9
180000 9 8 7
190000 8 9 8
200000 7 9 10
210000 8 7 8
220000 17 7 7
230000 9 10 9
240000 11 11 11
250000 20 10 8
260000 16 11 9
270000 13 12 11
280000 13 14 14
290000 14 12 12
300000 11 13 13
310000 12 11 14
320000 12 12 15
330000 13 15 16
340000 14 17 17
350000 14 14 10
360000 18 16 15
370000 15 18 14
380000 16 19 13
390000 16 20 15
400000 17 15 18
410000 17 16 18
420000 18 18 17
430000 17 19 19
440000 18 17 21
450000 18 21 22
460000 19 23 20
470000 20 25 21
480000 21 27 22
490000 23 26 23
500000 25 25 24
510000 25 25 22
520000 21 23 23
530000 23 25 25
540000 24 26 22
550000 25 26 23
560000 24 27 25
570000 26 28 24
580000 24 29 23
590000 28 30 25
600000 29 28 23
610000 27 27 24
620000 29 29 26
630000 30 28 23
640000 31 27 25
650000 32 30 25
660000 31 28 24
670000 29 29 23
680000 30 38 23
690000 32 37 24
700000 35 36 23
710000 34 34 24
720000 36 39 23
730000 32 41 24
740000 35 44 25
750000 36 42 25
760000 34 38 26
770000 38 39 24
780000 37 38 24
790000 9 48 24
800000 38 45 26
810000 35 50 25
820000 36 52 26
830000 37 53 25
840000 42 54 25
850000 43 56 24
860000 45 58 26
870000 44 57 22
880000 47 54 23
890000 48 56 24
900000 49 53 24
910000 46 51 25
920000 48 52 23
930000 50 53 25
940000 57 58 26
950000 52 57 26
960000 55 56 24
970000 55 53 25
980000 58 54 24
990000 59 54 26
1000000 66 58 26

Heap Sort:

Input Size Time in ms (Partially Sorted) Time in ms Random Time in ms Sorted
10000 1 1 2
20000 1 1 2
30000 2 2 4
40000 3 3 3
50000 5 4 4
60000 5 2 5
70000 6 3 6
80000 7 6 8
90000 11 8 9
100000 10 10 10
110000 10 11 10
120000 11 13 11
130000 26 14 13
140000 22 15 14
150000 17 16 15
160000 21 17 16
170000 17 18 18
180000 22 19 17
190000 27 19 19
200000 22 20 20
210000 22 25 21
220000 34 23 23
230000 23 23 24
240000 39 26 26
250000 34 28 27
260000 40 30 28
270000 35 32 29
280000 42 33 30
290000 40 36 31
300000 31 35 35
310000 33 34 35
320000 35 36 36
330000 46 38 36
340000 40 40 37
350000 38 43 39
360000 41 45 39
370000 45 48 40
380000 43 47 42
390000 14 49 45
400000 40 48 44
410000 45 49 43
420000 47 50 45
430000 48 50 46
440000 54 52 48
450000 56 53 47
460000 57 56 49
470000 58 57 50
480000 57 58 51
490000 56 57 53
500000 52 58 54
510000 58 59 56
520000 58 62 55
530000 62 63 55
540000 63 64 56
550000 61 65 58
560000 60 69 61
570000 62 68 63
580000 63 67 65
590000 64 69 63
600000 65 74 68
610000 63 72 69
620000 63 71 70
630000 62 70 71
640000 65 72 72
650000 70 74 74
660000 72 76 75
670000 75 78 75
680000 79 81 76
690000 82 83 78
700000 84 86 79
710000 86 89 81
720000 87 93 83
730000 89 94 85
740000 90 96 84
750000 95 95 83
760000 93 96 86
770000 94 96 85
780000 109 99 84
790000 103 98 83
800000 105 105 87
810000 104 105 90
820000 105 106 92
830000 106 108 93
840000 110 110 94
850000 112 111 95
860000 118 112 96
870000 117 115 97
880000 114 118 98
890000 120 119 99
900000 124 120 100
910000 123 121 100
920000 126 123 102
930000 128 124 104
940000 130 125 105
950000 135 123 108
960000 134 127 108
970000 135 123 110
980000 136 126 114
990000 137 126 118
1000000 139 128 120

Intro Sort

Input Size Time in ms (Partially Sorted) Time in ms Random Time in ms Sorted
10000 0 0 0
20000 0 1 0
30000 0 2 0
40000 2 0 0
50000 0 0 0
60000 0 3 0
70000 0 0 0
80000 0 1 0
90000 1 1 0
100000 1 5 1
110000 1 4 1
120000 1 6 1
130000 2 4 1
140000 2 3 1
150000 6 5 1
160000 3 4 1
170000 3 3 1
180000 3 5 1
190000 3 6 1
200000 6 7 2
210000 3 9 3
220000 3 8 3
230000 5 8 5
240000 7 7 6
250000 5 6 4
260000 5 8 7
270000 6 8 8
280000 9 7 8
290000 7 8 8
300000 6 9 8
310000 6 9 8
320000 6 9 8
330000 6 9 8
340000 6 7 8
350000 7 10 8
360000 7 10 8
370000 7 10 8
380000 12 10 10
390000 9 10 9
400000 10 10 10
410000 11 15 11
420000 12 13 14
430000 13 15 13
440000 14 14 13
450000 15 13 13
460000 12 15 13
470000 13 16 11
480000 15 14 12
490000 14 12 14
500000 13 14 9
510000 13 13 7
520000 13 15 8
530000 13 14 11
540000 15 13 12
550000 14 14 13
560000 16 17 14
570000 18 18 13
580000 17 17 16
590000 18 16 13
600000 19 15 13
610000 21 16 14
620000 23 14 13
630000 25 12 13
640000 24 13 13
650000 23 15 15
660000 22 15 18
670000 18 13 13
680000 19 10 11
690000 17 14 14
700000 18 13 11
710000 20 10 12
720000 23 10 16
730000 21 15 14
740000 22 16 13
750000 22 18 13
760000 22 21 15
770000 21 22 14
780000 18 23 13
790000 19 24 16
800000 18 25 13
810000 19 24 12
820000 20 26 15
830000 20 25 14
840000 20 24 13
850000 21 23 16
860000 23 25 17
870000 22 27 18
880000 21 28 14
890000 22 24 11
900000 23 26 12
910000 22 28 13
920000 21 24 14
930000 25 25 11
940000 24 26 16
950000 23 24 17
960000 25 23 18
970000 24 24 13
980000 23 28 13
990000 24 28 14
1000000 31 29 18

Graphical representation of time-complexity:

Quick Sort Graph

Heap Sort Graph

Merge Sort Graph

Intro Sort Graph

Clone this wiki locally