Sorting and efficiency

We learned about sorting algorithms in CSC148 and the topic on their efficiency is worth talking about.

There are many sorting algorithms and they can be classified by different standards. Specifically, there two types of sorting algorithms, one is a comparison sort, which means it examines the data only by comparing two elements with a comparison operator, another is called non-comparison sort. Comparison sort includes quick sort, merge sort, bubble sort, insertion sort and selection sort. Today I will just talk about comparison sort.

I remember the first sorting algorithm I learned might be bubble sort. Bubble sort works by scanning through the list repeatedly, and then compare adjacent items and swapping them if they are in the wrong order. When no swaps are needed, the list is sorted. Its average performance is O(n^2). In the lab, we showed that bubble sort is the slowest among all the sorting algorithms we are testing, which means it is not a practical sorting algorithm for large data.

Selection sort is easy to understand. This algorithm divides the input list into two parts: the sorted part and unsorted part. In the beginning, the sorted part is empty and the unsorted part is the entire input list. Then the algorithm finds the smallest (or largest) element in the unsorted part, swap it with the leftmost unsorted element and puts it in sorted order. The time complexity of selection sort is O(n^2) , for we have to compare the item we got with all other items.

Now let’s take a look at two fast sorting algorithms: quick sort and merge sort. Their average running time are all O(nlogn). Quick sort is a divide and conquer algorithm and it is recursive. It divides the list into two smaller sub-lists and then it recursively sort the sub-lists. The base case of the recursion is lists of size zero or one, which never need to be sorted.