Week 11: Sorting and Efficiency

Throughout this course, CSC148, we have covered three major topics of computer science: the ideas of object oriented programming, recursion, and sorting and efficiency of sorting algorithms. Having already spoken to you, the reader, about the former two topics I will spend this week discussing the latter, and its implications on my learning experiences and what I am going to take away from this course.

Sorting algorithms are used to sort through arrays, or lists in python, in an effort to find out if the object you are searching for is included in said array or not, usually returning a boolean statement of true or false for the result. I can see that the uses for sorting algorithms can extend far past simply looking through a list in hopes of finding some number, but rather its applications into databases, and how the efficiency of sorting algorithms can make a very large difference when searching into a database as large as, for example, serial numbers for all the products in all Costco stores across the world. Such a array in this database and can extend into the trillions of items, if not more, and when inventory needs to be conducted and barcodes are scanned to be cross-references with their place in the database, an efficient sorting algorithm that takes O(logn) will be much faster than a sorting algorithm that takes O(n^2). With many other real world applications the knowledge of algorithm efficiency will be very useful to me, especially when I will learn more effective methods for reducing algorithm run time for average case and worst case scenarios. 

Having already discussed specific sorting algorithms and their efficiency in the previous week, specifically merge sort and quick sort, I will not spend time discussing more as they were both great examples of efficient algorithms that are some of the most used and taught across the world. However I will briefly state that Professor Heap's explanation of the sorting algorithms discussed in class using a deck of cards and going through each step of sorting on the projector really helped cement my understanding of how each sorting algorithm works. As well the readings selected by Professor Heap, specifically the reading "Sorting in Interactive Python" with it's interactive python visualizer of the algorithm code, its step by step visualizations of the sorting algorithms steps, and the informative descriptions provided for each sorting algorithm were also a huge help in my understand.

In conclusion, I am glad that sorting and efficiency were taught so thoroughly in CSC148 and I understand and appreciate their importance and applications for computer science and the real world. 

Until next wee...oh right, this is the last week of the SLOG :'(. Farewell then my fellow SLOGers, TAs and Professor Danny Heap,

Maxim Isakov 

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