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²). For best-case scenario (already sorted elements) insertion sort has better complexity – O(n).

Complexity: O(n²).

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) or just O(n²) complexity.

Complexity: O(n²).

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) or just O(n²) complexity.

Complexity: O(n²).