Logan Ortega 1 CMPSC 130A PA4 Bubble Sort Insertion Sort Quicksort Merge Sort Profiling ABSTRACT Upon pro ling the implementation of Bubble Sort Insertion Sort Quicksort and Merge Sort algorithms the evidence clearly provides a ranking based on time complexity The basis of this report will be the comparison of runtimes for the four sorting algorithms with various sample patterns ordered increasingly ordered decreasingly and no order The following content of this report will consist of multiple graphs illustrating the relationship between the above sorting algorithms as well as a brief description and analysis of the graphs and their signi cance Note the x axis represents the sample size in increments of one thousand element while the y axis shows the relative time complexities Additionally it should be emphasized that the y axis is time complexity and not processing time The range for processing time would be far too large to visualize the relationships between the sorting algorithms on a graph so select sorting algorithms were proportionally scaled down to t on the graph with the remaining sorting algorithms For example for the increasingly ordered case the processing time of the Bubble Sort was divided by 1000 to match the range of the other sorting algorithms Since this report is focused on the time complexities of the sorting algorithms and not their processing times this is rather trivial and will not be discussed for the remainder of this report CASE 1 ORDERED INCREASINGLY The rst case of observance comes from comparing the four sorting algorithms when sorting a set already increasingly ordered Graph 1 illustrates the relationship between each sorting algorithm and its time complexity when sorting a set of this pattern Bubble Sort runs in O n Insertion Sort runs in O n Quicksort runs in O n log n and Merge Sort runs in O n log n To conceptualize these relationships we must refer to each algorithms methods of sorting Bubble Sort and Insertion Sort are both running in linear time because an already ordered set is the best case for both of these algorithms Both of these algorithms only have to make one pass because the set is already sorted Visually we can see Quicksort and Merge Sort are both running in O n log n Graph 1 CASE 2 ORDERED DECREASINGLY The second case of observance comes from comparing the four sorting algorithms when sorting a set already decreasingly ordered Graph 2 illustrates the relationship between each sorting Logan Ortega 2 algorithm and its time complexity when sorting a set of this pattern Bubble Sort runs in O n 2 Insertion Sort runs in O n 2 Quicksort runs in O n log n and Merge Sort runs in O n log n To conceptualize these relationships we must refer to each algorithms methods of sorting Bubble Sort and Insertion Sort are both running in exponential time because a reverse ordered set is the worst case for Insertion Sort and Bubble Sort is simply running an average case Visually we can see Quicksort and Merge Sort are both running in O n log n Graph 2 CASE 3 NO ORDER The third case of observance comes from comparing the four sorting algorithms when sorting a set that has no order Graph 3 illustrates the relationship between each sorting algorithm and its time complexity when sorting a set of this pattern Bubble Sort runs in O n 2 Insertion Sort runs in O n 2 Quicksort runs in O n log n and Merge Sort runs in O n log n To conceptualize these relationships we must refer to each algorithms methods of sorting Bubble Sort and Insertion Sort are both running in exponential time because a set with no order is simply an average case for both algorithms Graph 3 Visually we can see Quicksort and Merge Sort are both running in O n log n CONCLUSION The case in which the set has no order is the best case to obtain a de nitive ranking of the time complexities of the four sorting algorithms This is because all four sorting algorithms are running an average case with no special circumstances Although Bubble Sort and Insertion Sort both run in O n 2 it is clear from the graph plots that Bubble Sort would have longer processing times than Insertion Sort Similarly Quicksort and Merge Sort both run in O n log n but Merge Sort would have longer processing times than Quicksort Logan Ortega 3 BUBBLE SORT Best Case O n Already sorted set Average Case O n 2 Worst Case O n 2 Smallest element of set is in the last position INSERTION SORT Best Case O n Already sorted set Average Case O n 2 Worst Case O n 2 Reverse ordered set QUICKSORT Best Case O n log n Average Case O n log n Worst Case O n 2 A pivot is selected as the largest or smallest element in the set MERGE SORT Best Case O n log n Average Case O n log n Worst Case O n 2 At every merge step exactly one value remains in the opposing list no comparisons were skipped