Sorting and Effiency

In CSC108, we were introduced to three kinds of sorting algorithms, insertion, bubble and selection sort. Again at the end of the CSC148 semester, we learned two more sorting algorithms, quick sort and merge sort. A sorting algorithm is an algorithms that puts elements of a list in a certain order. In the following, I am going to talk about various kinds of sorting algorithms and its efficiency. In addition, we usually use different big-oh notations to express the complexity of each algorithms. 

Quicksort is something new to me, but after compare the running timing for 1000 item list, it turns out that it is a very efficient sorting algorithms. By using quicksort, we usually find a good pivot so that we can compare the items after the pivot. If the item is larger, we put it in front of the pivot, and vice versa.
In most cases, we choose the first item of the list as a pivot, and repeat the quicksort until the list is sorted. This kind of algorithm is usually used for large size of data. Its best case complexity is o(nlogn), but worst cases is o(n^2).
Merge sort is different, it splits the list into half, sort the two halves, and merge the sorted list again. By using the recursion, we can sort the whole list using this technic. The whole process remains the same no matter what list is given so that its complexity is o(ologn) for all cases.

Insertion sort works by moving the next item to its proper position in the sorted part of the list at beginning. This sorting algorithm the most basic algorithms but not very efficiency. Its complexity is o(n^2) for worst cases.
Bubble sort works by going over the list and place each item to its final position. It compare each item to the whole list and swap the one after it so that after each iteration, the final item must at the right place. Despite its worst complexity is the same as insertion sort and selection sort, bubble sort is the most inefficient sorting algorithm according to lab10's analysis.

Binary tree sort is very similar to the merge sort algorithms, since the structure of a binary search tree provided a good path for sorting. In a BST( binary search tree) node, the left children must be less than the root, mean while, the right children must be larger than the root. Under this condition, to sort the list, we just need to compare half of the items in the list. Its worst complexity is o(nlogn) just as merge sort.

Selection sort selects the smallest remaining item repeatedly and puts it to the proper position it belongs. This algorithm have the worst complexity o(n^2) because for each item in a n size list, it has to go over the whole list to find its position as well as its best complexity. It is not very efficiency.