
Sorting: Insertion Sort
In this post I will implement another basic sorting algorithm – Insertion Sort. The idea of the algorithm is as follows:
 starting from the beginning of the list compare value with the elements on the left (if any)
 swap their position if they are not in the right order
 continue until element on the left is smaller than current element
 after each iteration elements on the left from the current element are sorted
We can visualize insertion sort algorithm by sorting following list [5 1 4 2 8]. I’ll use colors to specify current adjacent pair and already sorted elements.
Iteration #1 : [5 1 4 2 8]
Iteration #2 : [5 1 4 2 8] [5 1 4 2 8] → [1 5 4 2 8]
Iteration #3 : [1 5 4 2 8] [1 5 4 2 8] → [1 4 5 2 8] [1 4 5 2 8] → [1 4 5 2 8]
Iteration #4 : [1 4 5 2 8] [1 4 5 2 8] → [1 4 2 5 8] [1 4 2 5 8] → [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]
Iteration #5 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]
Implementation of the insertion sort is very simple:
Similarly to bubble and selection sorts we have two loops: outer and inner, so the average complexity is similar as well – O(n^{2}). For bestcase scenario (already sorted elements) insertion sort has better complexity – O(n).
Complexity: O(n^{2}).

Sorting: Selection Sort
In this post I will implement another well know sorting algorithm – Selection Sort. The idea of the algorithm is quite simple:
 divide input list into two parts: sorted (built up from left to right) and unsorted (remaining items to be sorted)
 initially sorted part is empty and unsorted part contains input list
 starting from the beginning of the unsorted part find the smallest element in the list
 swap its position with the left most element in the unsorted part
 after each iteration move sorted / unsorted boundary by one element to the right
We can visualize selection sort algorithm by sorting following list [5 1 4 2 8]. I’ll use colors to specify currently smallest unsorted element, current unsorted element and already sorted elements.
Iteration #1 : [5 1 4 2 8] [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [1 5 4 2 8]
Iteration #2 : [1 5 4 2 8] [1 5 4 2 8] → [1 5 4 2 8] → [1 5 4 2 8] → [1 5 4 2 8] → [1 5 4 2 8] → [1 2 4 5 8]
Iteration #3 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8] → [1 2 4 5 8] → [1 2 4 5 8]
Iteration #4 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8] → [1 2 4 5 8]
Iteration #5 : [1 2 4 5 8]
Implementation of the selection sort is quit simple:
As with bubble sort we have two loops: outer and inner. Outer loop is executed for each element (n times) and inner loop is executed for n/2 elements on average. As a result we have O(n^{2}/2) or just O(n^{2}) complexity.
Complexity: O(n^{2}).

Sorting: Bubble Sort
In this post I will implement very basic sorting algorithm – Bubble Sort. The idea of the algorithm is very trivial:
 starting from the beginning of the list compare every adjacent pair
 swap their position if they are not in the right order
 after each iteration the last element is the biggest in the list
 after each iteration one less element is needed to be compared
 continue until there are no more elements left to be compared
We can visualize bubble sort algorithm by sorting following list [5 1 4 2 8]. I’ll use colors to specify current adjacent pair and already sorted elements.
Iteration #1 : [5 1 4 2 8] [5 1 4 2 8] → [1 5 4 2 8] [1 5 4 2 8] → [1 4 5 2 8] [1 4 5 2 8] → [1 4 2 5 8] [1 4 2 5 8] → [1 4 2 5 8]
Iteration #2 : [1 4 2 5 8] [1 4 2 5 8] → [1 4 2 5 8] [1 4 2 5 8] → [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]
Iteration #3 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]
Iteration #4 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8]
Iteration #5 : [1 2 4 5 8]
Implementation of the bubble sort is quit simple:
As you can see we have two loops: outer and inner. Outer loop is executed for each element (n times) and inner loop is executed for n/2 elements on average. As a result we have O(n^{2}/2) or just O(n^{2}) complexity.
Complexity: O(n^{2}).