Sorting And Efficiency

Last semester, I learned a decent amount about sorting and efficiency in CSC108. The main sorting algorithms I learned about were Bubble sort, insertion sort, and selection sort. Efficiency was touched upon, atlthough not as in depth as CSC148. I mostly learned about analyzing the best case and worst case. Best case is the least amount of steps possible the algorithm could perform while worst case is the most amount of steps possible the algorithm could perform. All of this depends on how the initial list is sorted. In CSC148, we learned about a couple of new sorting algorithms including merge sort and quick sort. From my understanding, merge sort splits lists approximately in half into smaller sublists. It then compares a pair of sublists and "merges" them into one sorted list. It does this by comparing the smallest value in each sublist, then putting the smaller value into the new merged list. From what I learned in class, the efficiency of this would be affected by how many times the list has to be split. Generally, no matter how a list of a certain size is sorted, the performance of this algorithm will generally be the same--unless the list is already sorted. Quick sort picks a pivot at random and sorts the values smaller than it to one side and values greater than it to the other side. Quick sort keeps doing this until the list is sorted.  I learned in class that depending on the pivot chosen for quick sort, the efficiency of it could be seriously affected(Example: If the pivot was the smallest value, it made it harder to sort). Danny solved this problem by making the pivot always random. Therefore from what I learned, if n amount of items are to be sorted by quick sort and merge sort, the performance of quick sort will vary more than that of merge sort. In terms of measuring algorithm performance, CSC148 introduced us to Big-Oh. Big-Oh measures the upper-bound of a function and is used as the symbol beside a certain run time of a function (Example: Linear run time is O(n) and quadratic run time is O(n^2).