#13 Sorting Algorithm

This is final post of the semester...

Sorting Algorithms:
Bubble, Selection, Insertion, Merge Sort, Quick Sort.

Bubble Sort
First I would like to discuss Bubble sort the very old fashion. Bubble sort is the very intuitive way for human beings to sort. However this sorting algorithm is takes the longest for computer to execute due to the nature of it. Based on the Big-O theory, the amount of time it takes to complete the whole sorting process is n^2 which is considered very long. However, it is not always the worst choice. For instance, when sorting a small list, it could be a good alternative to use bubble sort since the size of the list to be sorted is rather small. However, it is definitely not a good way when the size of the list is huge.

Selection Sort:
Selection Sort works by repeatedly selecting the smallest element list and putting it to right place. This algorithm is better than Bubble Sort since it get rids of the unnecessary comparisons. Every time we select out the smallest element that's in the unsorted pile. At the beginning, the unsorted list is of size n, which gradually reduces to 0 as we sort through the list. So the Big-O would be 1+2+...+n which is (n^2+n)/2 which has a asymptotic curve of n^2/2. So the amount of time to sort a list of large size would be a factor of 0.5 as opposed to Bubble Sort.

Insertion Sort
Insertion Sort is done by repeatedly inserting the next item in the already sorted portion of a list. Again this is improved based on Bubbly Sort and the amount to run through the sorting is about 1/2 of what it takes in Bubble Sort.

Merge Sort:
Recursively divide the unsorted list and sort them into sorted order, then merge them with other sorted portions. This sorting algorithm inevitably employs recursion and the amount of time to complete the sorting has nothing to do with the unsorted list. No matter how messy the list is the Big Oh would be nlogn. This works better when the unsorted list is of large size and it would be very time consuming to employ the above sorting algorithms.

Quick Sort:
Recursively select a Pivot and break the list into two sublists which are of either smaller or larger values than the 'Pivot'. Again this can only be done with the help of recursion. It should also be noted that the algorithm works the worse when we have a 'reversed' list. The way to go around this scenario is to randomize the selection of the 'Pivot' such that we can reduce the number of computations.

Based on the lab 9, there are many things that we can do to improve the performance of the algorithms discussed above.

Bubble Sort:
Use a temporary variable to store the length of the list so we don't need to use the built-in len() function to evaluate the length of the unsorted list over and over.

Insertion Sort
Use built-in del() instead of moving all the elements that follow the element deleted.

Quick Sort:
Refer to above.

Last couple comments:
Timsort:
Make use of all the algorithms discussed above and choose the best possible way to sort the list.

Count Sort:

Great for large sizes list but has limitations on the relationship between the list size and the variation between the largest element and the smallest element of the list. If the conditions are not satisfied, the algorithm would not work.

#12 Topics covered in the last week

Map Reduce

As discussed in lecture slide, map reduce is sort of like list comprehensions. By introducing the concept of Map Reduce, we can combine iterables into a single reduced value. The basis of this concept is that many computations conducted can be treated as parallel such that we can reduce. For non-parallel computations, this concept may not apply. Just like the examples of list comprehensions, we generalize a list using a single expression, all the elements that will be generated can be treated as 'parallel' since the operations used to generate those elements are identical.

Tracing

We were introduced the following terminologies:
Local, Non-Local, Global.
Fairly simple concepts that were explained through a comprehensive example in class. Basically Global is variables that's in the global scope. Local only refers to the scope where the variable is evaluated. If a local variable that sits in global scope, then it is also a global variable. Finally, Non-Local refers to variables that sit one level above the current scope. For example, in the case of a helper function, a Non-Local variable would refer to the variable that sits in the function which calls the helper function.

Finally, Memorization

I previously employed this concept in Assignment 1. Basically this allows us to omit the redundant recursion calls by which we reduced the demand for the computer to compute and improve on efficiency. In assignment 1, I built a dynamic memory which memorizes the best cuts for cheeses starting for 1 cheese to n cheeses. By doing so I was able to find out the best cuts very easily based on the previous computations and utilized the information in execution. This is a great tool that we can use to reduce the unnecessary computations.