Selection sort

Selection sort is an \(O(n^2)\) sorting algorithm that works by searching through a list to find the minimum element and swapping it for the first in the list. After every swap, selection sort is performed on the list with the head removed (ie. the minimum element). Due to the way that elements are swapped anywhere in the list, this is not a stable sort.

Selection sort is similar in complexity to insertion sort but almost always performs worse. This is due to the fact that selection sort has an exact number of comparisons based on \(n\), which can be defined using the arithmetic progression:

$$(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2$$

This makes its best case always contain the same amount of comparisons as its worst.

While selection sort is faster than most \(O(\log n)\) sorts for small lists, insertion sort is normally the preferable choice. It's main favourable property is that it will perform at most \(n - 1\) element swaps, so it may be useful if swapping is expensive.

Quicksort

Quicksort is an \(O(n^2)\) sorting algorithm that runs in \(O(n \log n)\) time on average. It has a number of favourable qualities; it's an in-place sort, requiring \(O(\log n)\) auxiliary space in the worst case; and is also a divide and conquer algorithm making it easy to parallelise. Unfortunately however it's not a stable sort.

It works by first selecting a 'pivot' element, then re-ordering either side of the list so that everything before the pivot is less than the pivot and everything after is greater. Quicksort is then called recursively on either side of the pivot.

Despite quicksort having a worst-case performance of \(O(n^2)\), it is sometimes regarded at the same level performance-wise as \(O(n \log n)\) sorts like merge sort or heapsort. This is due to its average case being \(O(n \log n)\), it will often perform even better in practice than the \(O(n \log n)\) sorts.

Heapsort

Heapsort is an \(O(n \log n)\) sorting algorithm that works by first constructing a heap out of the list and repeatedly pulling the root off the top of the heap and reconstructs it until there are no items left in the heap. The values that are pulled off of the top of the heap come out in sorted order. If the heap used was a min-heap, the resulting list will be in ascending order, and a max-heap will give them in descending order.

Unfortunately heapsort is not stable so sorting a list that is already sorted could quite possibly end up in a different order.

Insertion sort

Insertion sort works by looking at each item in an array (starting with the second) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next item.

As you probably guessed, insertion sort isn't one of the fastest sorts, running in \(O(n^2)\) worst case time. It does have a few benefits however:

• It is faster than most \(O(n \log n)\) sorting algorithms for small lists.
• It is very memory efficient requiring only \(O(1)\) auxiliary space for the single item that is being moved.
• It is a stable sort; equal elements appear in the same order in the sorted list.
• It is an adaptive sort; it's fast when sorting mostly sorted lists or when adding items to an already sorted list.
• It is really easy to implement.

Merge sort

Merge sort is a sorting algorithm that runs in \(O(n \log n)\) time. It is a divide and conquer algorithm, so it can get the most out of today's multi-cored systems. It works by continually splitting up the array until each item stands on its own. The items are then merged back with the items that they were split with in the correct order.

Merge sort is also a stable sort, this means that if there are elements considered equal, they will be in the same order in the final list. This is illustrated in the below image, teal and blue (9) are in the same order in both the source and sorted lists.

Big-O Notation

Introduction

Big-O notation (pronounced 'Big Oh') is used in computer science as a means to describe the worst-case performance of an algorithm. It's one of the things you really should learn if you're interested at all in designing efficient algorithms.

The formal definition is as follows:

f(n) = O(g(n)) means c*g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c*g(n), for large enough n (i.e. , n ≥ n₀ for some constant n₀).

The Algorithm Design Manual, Steven S. Skiena

This definition is a very format way of saying that Big O-notation is the upper-bound/worst-case of a function.