Logan Ortega!1CMPSC 130A: PA4!Bubble Sort, Insertion Sort, Quicksort & Merge Sort Profiling !ABSTRACT!!Upon profiling 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 significance. 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 “fit” 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 first 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)). !!!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 Graph 1Logan Ortega!2algorithm 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)). !!!!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. 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 definitive 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. !!!!!!!!!Graph 2Graph 3Logan Ortega!3BUBBLE 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