Week 11: Sorting and Efficiency

This week we learned about sorting, which was also a topic on CSC108 and CSC165.

Before starting to discuss the different kind of sort, it is important to know that the focuses here is on the size of input, n. How does input size affect the time requires to produce output with different kind of sort (algorithm)?
Sometimes, the list might already be sorted, but what we care about more is the maximum steps (the worst case) require to sort a list. We call this big-O, or O(n), where in this case it means the maximum steps to sort the list with size n is n (or it runs no more than n steps).


Selection Sort:
Selection sort set the first item in list as i and swap the value in its position with the smallest value in list while i moves along the list.
It has O(n^2) because it requires n-1 steps for i to check the list with length n, and swap the value n-1 times if the list has the worst case such as [5, 4, 3, 2, 1].

Insertion Sort:
Insertion Sort set the first item in the list as i and compare + sort it with i-1 while i moves along the list.
The worst case for insertion sort is n^2, O(n^2). i needs to check n-1 times for each list with length n, if the list has a worst case such as L = [5, 4, 3, 2, 1], it will also need to swap i and i-1 for n-1 times.

Merge Sort:
Merge sort keeps divide the list into two until it has only one item After done splitting all the items, it combine the two item together, compare and swap the item in order before it merge.
Merge sort has an O(nlog n) algorithm, since it will require log n steps to split a list into two items and n steps to merge them together again.
Below is a picture from the reading the professor provided.

split the list until only one item left

sort and merge the two items

Quick Sort:
Quick sort set a random value (usually the first one) in list as the pivot. For the rest of the item in list, it set a left mark and right mark on the very left and very right of the list and starts to compare them with the pivot while moving along the list. If the item in the current left mark is bigger them the pivot item plus if the right mark item is smaller than the pivot item, the two value swap and the marks move to the next index to compare again. In the end, we will have a list with value smaller than the pivot and a list with value bigger than the pivot. We put the pivot item between the two lists so it is sorted, then do the same thing (quick sort) again for both left and right list.
Quick sort has O(n^2), based on if the list has a split point at the very end of the list, in other word, sorting a list of 0 items and a list of size n-1. Then sorting another list of 0 items and list of n-2 items for list n-1, and so on.
Below are pictures from the reading the professor provided.
n

first quick sort