Week 11 - Sorting and Efficiency

Through the past weeks of class the main topic of discussion is sorting and efficiency. Sorting is the process of placing elements in a list into a certain order. Before taking a look at bigger sorting algorithms and concepts it is important to understand the basic necessities. Firstly, you have to be able to compare two different pieces of information and secondly to exchange that piece of information. All the most popular sorts that we have learned implement this in a way (bubble sort, insertion sort, etc.). The idea of sorting was at first glance mostly a review, therefore the topic where not to out of reach for me to grasp. I understand the basics of sorting and also the many different methods of sorting that can we used. I see where how sorting is important to computer science as many different people have thought of many different ways of sorting. Also I can understand that sorting is an important function in computer science (e.x sorting databases based on specific labels)

Another topic covered in the past few weeks has been Big O notation. Big O notation describes the limiting behaviour of a function. For sorting purposes this describes the best case runtime of sorting function based on input size n. We tested this in the Lab in week 10. We had to run each sorting algorithm on a list of items and see how the runtime changed with different factors (sorting, random). What we learned from this lab that certain sorting functions are better based on these factors. Another important fact about sorting is that merge sort and quick sort at O(nlog(n)) is the fastest runtime of a sorting algorithm. This is compared to other sorting algorithms at O(n^2), O(n), etc. After looking at each algorithm I begin to get an appreciation for what it takes to make an efficient algorithm. What I found hard about Big O notation is that it is hard to understand how runtimes are derived from the function. I will have to read more in depth into how every algorithm works so that I can get a better understanding of how they all work and how their runtimes compare and why they are a certain time.