Sorting and Efficiency

Big-Oh. What a fantastic term. When I first saw it, I was completely confused what it meant or what purpose it served. Matter of fact, I came across it after I was ill for a week and was catching up. I was impressed with how fundamental efficiency, and big-Oh, big-Theta, and big-Omega, were in the field of computer science. At around the same time it was being covered in CSC148, it was also being covered in CSC165. I feel like that enhanced my understanding of the concept, as I not only understood the efficiency of programs, I had to recognize it and prove it.

Sorting is evidently a key component in programming. By working with sorted values, it becomes easier to find a given objects. In addition, it allows for a certain level of organization to be present in the data being manipulated by the code. Many sorting algorithms have emerged, each with their own efficiency benefits. It ultimately comes down to the size of the list to determine whether or not the more "advanced" algorithms are necessary, or whether they would actually extend the time needed to sort in the first place.

But this seems to only be looking at sorting at a very basic level. I find the different sorting algorithms to be very interesting when they are compared from an efficiency standpoint. First I examined the three methods of sorting that we were taught last term in CSC108: bubble sort, selection sort, and insertion sort. Efficiency was briefly touched upon, but only in reference to the best and worst cases. Looking back, bubble and selection sort's efficiencies were big-Theta(n^2). Insertion sort was possible more efficient, with the upper bound being n^2, but the lower bound being n. In addition, I recently examined quicksort. While it has the same worst possible runtime, it's average runtime is significantly faster than the three previously mentioned functions, as it is O(n*log(n)). I guess that's why it is called "quicksort".

This is all very interesting, but ultimately, what is it's significance? While I think that efficiency was most easily visualised in sorting functions, it has a much greater role in programming overall. At the fundamental level, efficiency can mean the difference between a usable/functional program and one that isn't. Maximizing efficiency is crucial for ever step of the way, as poor efficiency can become exponentially worse in a program.

So that's my last SLOG. It's not pretty, it's not fantastic, but it's an honest reflection of what I've learned. Bye guys :)