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²).