week 11 - sorting and efficiency

Sorting and Efficiency
sorting is the process of placing elements from a collection in some kind of order. For example, a list of words could be sorted alphabetically or by length. A list of cities could be sorted by population, by area, or by zip code. There are may sorting algorithms that have been developed and analyzed. This suggests that sorting is an important area of study in computer science.
In CSC108, I have learn three sorting method: bubble sort, selection sort and insertion sort. The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. The insertion sort always maintains a sorted sublist in the lower positions of the list. Each new item is then 'inserted' back into the previous sublist such that the sorted sublist is one item larger.
In CSC148, I learn two more sort method：merge sort and quick sort. Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by base case. If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage. A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.
When taking about the efficiency of these five sort, we need a Big O notation, which provides an upper bound for the runtime of our algorithm. For the average case, Big O of Bubble sort, insertion, selection sort is O(n^2). However, Big O of Quick sort and Merge sort in average case is O(nlog(n)). We can see that the quick sort and merge sort is more efficient than that three sort. From this, we can know that learning the efficient of a method is very important.