Week 10:Sorting and Big Oh

This week in CSC148 we had assignment 2 part 2 due on Thursday and both lectures in the week kicked off with encouraging words and helpful tips from Professor Heap.

In our readings this week we looked at many sorting algorithms such as, bubble sort, insertion sort, selection sort, etc, their code, their descriptions and what their time complexity was in terms of Big Oh.

During lectures we analyzed 2 specific searching algorithms, quick sort and merge sort.

Quick sort works as a divide and conquer solution, where a pivot is chose, sometimes at random, and then it is place in its correct sorted index with in a list. Then the list is divided into two sub-lists that are lower indices than where the pivot is situated or higher. These subsequent lists are then also quick sorted recursively until more sub-lists are created if need be, and thus eventually all items in a list will be selected as pivots and be sorted into their correct place in the list. The big Oh complexity we found depends on how many times we choose the pivot multiplied by log(n) since we divide the list in half at every step, thus big Oh of quick sort is O(nlogn). Here is a diagram visualizing the process:

The second algorithm we looked at, merge sort, which is also a divide and conquer type of searching algorithm. Merge sort works by dividing lists in half until there are n number of lists of length 1. Then lists in pairs of 2 are compared with each other and sorted into a a larger list from smaller to larger. This process continues until a completely sorted list is completely and thus merge sort is completed. Big oh complexity of merge sort is also O(nlogn) because we divide the list in half until we reach length 1 lists, thus log(n) and then this is multiplied by n because we need to build the list back up in order to complete the sorted list, and this depends on the size of n. Here is a diagram visualizing the process:

This week taught me that algorithm efficiency is truly important for sorting algorithms, especially when the length of the lists move into extremely large numbers. I have also learned that some algorithms behave differently in their average case rather than their worse case and will thus be more suitable for certain situations, while other algorithms will be better for other situations.

Until next week,

Maxim Isakov