Sorting Fun

Sorting. A big area of computer science due to its usefulness in a number of algorithms. Sorting is the process by which the elements in a list are put in a determined order. In selecting the method to sort a list of items, it's important to consider the efficiency of the sort in handling the cardinality, as well as the conditions of the input elements. One sort could be more efficient for a larger-sized input where another sort could be more efficient in handling smaller-sized inputs. On a similar note, a sort may perform better or worse depending on the order that the elements of the list are already in.

In essence, two things occur in a sorting algorithm.

1 - Two elements are compared against each other.

2 - The elements are exchanged as necessary.

Here are two examples of sorts:

Quick Sort

Quick sort is a sorting algorithm that involves recursion. A 'pivot' value is selected and from there on, the list is broken up into two halves where all values bigger than the pivot exist on the right of the pivot, and all values smaller than the pivot exists on the left of the pivot. These sorted sublists are recombined and the sorting algorithm continues until the whole list is combined.

A note on efficiency:

The efficiency of quick sort depends on the pivot that you select, as well as the aforementioned 'condition of the input elements' (i.e. is this list sorted already). If a 'good' pivot is selected, this means the list is split at each step into halves that are approximately equal, then quick sort would perform in the efficient way that is hoped. In contrast, a 'bad' pivot would see the list being split up into uneven parts, in which more work would have to be done in the half that contains more values (in the worst case, you would get one half of size 1, and the other of size n-1). From this, it's easy to see that if a quick sort is run on a list that's already been sorted, if the pivot point that is chosen is the first value of the list, it would be the worst-case scenario in terms of efficiency using the quick sort.

Merge Sort

Merge sort is similar to quick sort in that it also relies on recursion and the splitting of the list into halves. However, merge sort begins by splitting the list into two halves that are of equal cardinality. This splitting continues down to the base case. Along every step of the way, the smaller element is taken between the two lists and joined together. The process continues until the entire list is sorted.

--

In class, we learned about the Big-O notation which goes into conveying the efficiency of the worst-case scenario. Initially I found the concept of the Big-O hard to grasp (because after all, there are so many different algorithms, and so many different ways to implement them, how is Big-O supposed to standardize the expression of efficiency?). From scouring about, I came to learn that essentially, the efficiency of any algorithm can be modelled as a function of its input size. The Big-O notation expresses the worst-case scenario of the algorithm by  extracting the part of the function that causes the function to grow the fastest.

Up until now, my exposure to computer science has mainly been in application. Big-O notation has been in essence the first time I've seen the integration of some real math (and this is only the very tip of the ice berg) with computer science. I hear that Big-O notation is something that is touched upon more in CSC165, but a lot more in depth in second year. It's also in second year that we begin getting introduced to other types of notation, such as Big-Omega for expressing the best-case scenario. It will be interesting to learn more about exactly how an algorithm is optimized to perform efficiently, and through mathematical means.