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.

Week 7

Week 7

One of the most important topics in csc148 is about recursion. But sometimes recursion is very hard to track. But I think I have some good ways to understand and to track the recursion process.

One way is to trace the function calls and I learned this in Lab04, where we are asked to trace some functions, greatest common denominator and binary representation. The process helped me lot understand recursive functions. I think it is easy for people to have an ambiguous idea about recursion without tracing it. If you traced it, you will see it’s just a repetitive process of calling the same function until it satisfies some condition and then stops.

My advice about learning and understanding the recursion is to work step by step. The recursion is not so hard if you have a clear thought about what the functions does and what the base case is.