Sorting and Efficiency

The last week of the second term is around the corner! Only two more 148 lectures are left and I am almost done my year one! However, maybe the profs wanted us to feel the opposite rather excitement, so they decided to give us a hard midterm on last Wednesday. Well, at the beginning, I thought I might just give up this course or even CS. Thank God that I came up with the answers for each questions even though they were not perfect. Anyways, something is better than nothing on a test.

In these few weeks, we came across with sorting again just like what we did last term in 108. We first had some review on bubble sort, insertion sort, and selection sort. Afterward, the topic Big-Oh was added. Big-Oh function is the upper bound of the worst case run-time model of a particular algorithm. First of all, let's list out some of the new sorting algorithms that I learned in this week.

Assume we have a list of [8, 9, 0, 2, 5, 4, 3, 6, 1, 7]. Let's see what the sorting algorithms with do with it.

1) Quick Sort
We first need an element to be the pivot. We can just take the last element by convenience. Then, we split the list into two halves; the first half is those elements that smaller than 7, the other half consists those bigger than 7. Now, we have two other new lists: [0,2,5,4,3,6] and [8,9]. We then repeat the same process again by using recursion, taking the last element as pivot and split the list into two halves. At the end, we can combine all the elements from the smallest one to the biggest one and this gives us a sorted list.

2) Merge Sort
We need two function for this sorting method. The first one is called merge. We combine two sorted list into one sorted list by using Merge function. The other one is a function that recursively return Merge function on the two halves of a list. If we have  [8, 9, 0, 2, 5, 4, 3, 6, 1, 7]. We will split this list again and again down to [8], [9],[0], [2],[5], [4], [3], [6], [1], [7], then we call merge in each pair. Then we get [89], [02],[54],[36],[17]. Then we do the same thing again and at the end we would have a sorted list.

The efficiency of each sorting can be compared by their worst case runtime on the same object. The quick sort is faster than merge sort since the worst case big-oh of quick sort is n^2 and nlogn for merge sort.