Week 11 - Sorting and Efficiency

A sorting algorithm is basically placing elements of a list in their correct positions. Sorting can be both in ascending and descending order. In computer science there are many sorting algorithms that makes this job but with different runtimes and of course different efficiencies. There is this famous question about sorting algorithm; "What is the difference between sorting types?", for example; what is the difference between insertion sort and selection sort? Indeed, there is huge difference between these two sorting algorithms. In the best case(list is sorted) insertion sort takes n iterations for the input size n whereas selection takes n^2 iterations for the input size n. Consider a list with 100.000 items in it. For the best case, insertion sort iterates 100.000 times whereas selection sort iterates 10.000.000.000 times. Aim of sorting algorithm is to get this job done with most efficient way, so in this case a computer scientist would prefer insertion sort.

We have learnt some sorting algorithms last semester, for CSC108. However we didn't have any information about boundedness of these algorithms. In CSC165 we are still working on Big-O(upper bound), Big-Omega(lower bound) and Big-Theta(tight bound) which are directly related with these sorting algorithms. I am going to talk more about the Big-O notation. For example let's consider selection sort. In selection sort there are two nested loops and each loop iterates n times. Thus, with the given input size n, selection sort's both worst case and best case performances are represented as O(n^2)(since n*n is n^2). As the Big-O notation states there is and upper bound which is c*n^2, for n^2 iteration, where c is a constant number. There is a table that shows the most efficient runtime of programs. Sorting table: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) <  O(n^n)...
As we move from left to right in the inequality, the runtime gets bigger and bigger which means it gets less efficient.

As we can see from the graph O(1) is the most efficient one. Regardless of the input size, it takes a constant amount of time to run the program which is very efficient. In this lecture we've learned merge sort, another sorting algorithm. It takes O(n log n) for average-case, worst-case and best-case performances. What it basically does is, first it divides the list into two until it reaches the base level, which means to reach a level where it has single element. This takes log n steps with base 2 as it divides 2 for each step. If we consider a list with n items in it, it takes n iterations for each step, thus merge sort takes O(n log n) time to perform.

In conclusion a computer scientist carry about efficiency when the input size is very large, because the difference between small sized input results is usually negligible. If we have millions of inputs to take care then we should choose a sorting algorithm that is most efficient and in order to choose that, we should look at the left side of our sorting table. A computer scientist can save tons of time by choosing the right algorithm. As a consequence, sorting and efficiency is a very important concept that we cannot and should not ignore.