More Talk About Algorithms!

This week’s topics are sorting algorithms and efficiency. I have already talked a bit about quick and merge sort, but I will further expand on my previous thoughts.

The first sorting algorithm we learned about is selection sort. It has an average case performance of O(n²), which can make it very inefficient while sorting very large lists. Selection sort divides the given list into two: an unsorted list and a sorted list. It begins by finding the smallest item in the unsorted list, and swaps its place with the item at the beginning of the unsorted list (the leftmost item). Then, this sorted item becomes part of the sorted list. This process continues until every item in the unsorted list is sorted and the unsorted list is empty.

Even though selection sort is more efficient than some other O(n²) algorithms such as bubble sort, it is very inefficient in terms of large lists. For large lists, some more efficient algorithms are ones that have average case performances of O(nlog₂n). Some examples are quick sort and merge sort.

If you are looking for explanations of how quick sort and merge sort work, simply scroll down to read the past blog post that I wrote called ‘Some Algorithms…’. Now, merge sort and quick sort have the same best case and average case performances of O(nlog₂n). However, merge sort’s worst case performance is O(nlog₂n), while quick sort has a worst case of O(n²). This means that in terms of efficiency, merge sort is more efficient during the worst case and is more of a consistent algorithm.