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). 

Term Test 2,BST, Midterm, big O etc.

    For the midterm we learned about BST, big O and run time of algorithms.  Run time analysis tests the run time of algorithms and big O is whats used to classify these algorithms, one of the common method used for this is checking processing time and types of input. We have learned about this in more detail in CSC165. There are different run time of big O like quadratic, cubic, logarithmic... e.g. 2n^2 + 8, we can drop 2 and represent the run time as O(n^2). HEnce we can use big O to determine the best and worst case run times of algorithms. There are other run time analysis, but they are outside the scope of this course.

     We have also learned about Binary search tree, which is another important part of this course, it was tested thoroughly in exercises and TT2. BST is pretty much a sorted binary tree. In it left tree has values smaller than node and right tree has greater values. Run time in BST is for the most part O(logn) or logarithmic. Logarithmic run time is the most efficient run time for BST, the worst case run time is linear.

    These were the two main topics in addition to LinkedList i talked about before that were tested in TT2. These are pretty complex topics that need a lot of practice in lists, run times and recursion, and it takes alot of time to understand these concepts, this was reflected on the average results of the TT2, it is also a wake up call that alot of practice is still needed for Final.