This week we have been asked to discuss sorting functions and efficiency of functions. To discuss efficiency we have generalized the run time of algorithms using big-oh notation. The purpose of the big-oh notation is to express functions in the most general form of their behaviour. This ultimately relies on the most significant term in the function, meaning the term with the highest power. This is what we seek to analyze because we are interested in what our algorithms will do on sets of data that are very large. When we get to such large sets of data the terms of the function that are not of the highest power will become minute which leads us to the generalization we do in using big-oh notation.
After working so much with recursion in csc148 we were able to move on to more complex and efficient sorting algorithms than csc108 by using recursion. Two of the recursive sorting algorithms we discussed were merge sort and quick sort. The algorithm that I found most intriguing was quick sort because of its simplicity and I think it really captures the beauty and effectiveness of recursion. Quick sort simply creates two sublists of the list to be sorted. One list is created by taking all of the items that are greater than the item at the first index which will than also be sorted using quick sort and added to the left of the first element in a new list. Similarly the second list is created by taking all of the items that are greater than or equal to the first item which will then be quick sorted and added the end of the new list. This process will continue on each sublist there are only 1 items in the sublist. At this point we know the function has placed this item either to the left or right of the first item of the previous sublist so we know it is appropriate sorted position.
