Sorting and Efficiency

 This week professor has assigned a topic for sorting and efficiency, i have talked about efficiency in before but in this post i will discuss efficiency and how each algorithm works in detail.


  I will start with discussing efficiency of algorithms, we have learned about Big O for runtimes in this course e.g.  given a list of size n, an algorithm that checks each value in the list once would mean the algorithm's efficiency is O(n). An algorithm that compares each value in the list, against every other value would be an O(n^2) algorithm and a BST run time where nodes are compared will be logarithmic and so on. Now i wil discuss about sorting algorithms in a bit of detail.

Selection Sort: The most basic algorithm of the three is selection sort, it also has a reputation for being one of the most inefficient algorithm.which sadly results in it also being one of the more inefficient algorithms. Basically when we are given a unordered list, this algorithm first finds the lowest element and places it in the beginning, and continues doing this for the length of the list, this will eventually give a ordered and sorted list. Since it compares each element with another element it gives us a quadratic run time or O(n^2). 





Merge Sort: This is an interesting sorting algorithm. When given a list it divides the lists in sublists until each sublist has one item left in it. Then the algorithm compares the first and only element of each sublist and merges the smallest or largest(though it is consistent) to one list. This gives us n/2 sublist of of every 2 elements. Then the merge sort again compares the first elements of of every list and merge the smallest ones to new lists. Eventually this will give us a sorted and ordered list of the initial n elements. This algorithm has O(n*logn) efficiency since it splits the list logn times, after splitting it is inspected log n times, once for each merge.  Although the efficiency is more like lgn + nlgn efficiency, the smaller term is dropped when describing big O efficiency.


Quick Sort: This algorithm also has an efficiency of O(nLogn) similar to Merge Sort. When it is given an unordered list it takes the first element of the list and then using it as a reference partitions the list in sublists and every element that is smaller than that first element is appended to a new list, and every element that is larger goes in another list. Then this algorithm is applied to every sublist, eventually all theses sublists are combined with the smaller one going first and so on. Because there are n comparison per element we have a run time that is logarithmic or O(nLogn).