Week 9

This week, I would like to talk about sorting algorithms. Now, if there was one thing that I had learnt about these sorting patterns we could choose, is that we should NEVER use bogo sort, since apparently my partner and I learned about during the lab-it would take literally forever to sort even a list of 10 elements. 

In this Slog, I would like to touch upon, the major sorts that we had learnt this week-merge sort, quick sort and selection sort. Instead of talking about how each of them specifically works (which would be a waste of time), I will instead talk about their efficiency. You see, the key part in any type of sorting pattern, is to do it in the quickest amount of time possible. In theory, that time is constant time, that is every list can be sorted in 1 second, regardless of size. Unfortunately, that is not always possible. In order to measure the time it takes, we use the notation big Oh or O(n) , which is used to show how effectively the pattern can sort a list. When we have complexity of big O, like lgn(O) or O(n), that is considered good, and shows that this pattern is efficient at sorting a list.

Starting off with selection sort
Selection sort improves on bubble sort considering the number of passes, it swaps the largest in the list with the smallest consistently, however, the runtime is still O(n**2) and so is the runtime of insertion sort at the worst case which inserts a value in its correct place from beginning to end. 

Shell sort is also O(n**2) at worst - it splits a list into sublists and sorts the sublists before piecing the list together again. Merge sort is a recursive algorithm which constantly splits a list in half and sorts smaller lists before rearranging the split list together with a worst case runtime of O(nlogn).

 Quicksort improves upon merge sort because it does not use additional storage, it uses a pivot point, a value that is used to split the list and then calls itself recursively to sort smaller lists. Quicksort is on average O(nlogn) and faster than most O(nlogn) algorithms although, the worst case runtime, O(n**2), is rare. 

There is also Timsort (O(nlogn)), a hybrid sorting algorithm that merges insertion sort and merge sort. You can also measure the best case runtime (represented by big omega) and the average case runtime (represented by big theta). However, if someone needs a sorting algorithm to sort a lot of information at once or in various different orders, then an algorithm is only as good as its worst case. 

And there we have it!