Overview

Bubble sort is a simple sorting algorithm. This sorting algorithm is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. You might be familiar with this algorithm because since it is simple, it is probably the first sorting algorithm you were taught in a CS class.

Algorithm

Assume an array of numbers “3 1 7 9 4”, and that we want to sort the array from the lowest to the greatest element. The bold elements are the elements compared in each step.

First Pass
(3, 1, 7, 9, 4) => (1, 3, 7, 9, 4) swapping since 3 > 1
(1, 3, 7, 9, 4) => (1, 3, 7, 9, 4) no swap since 7 > 3
(1, 3, 7, 9, 4) => (1, 3, 7, 9, 4) no swap since 9 > 7
(1, 3, 7, 9, 4) => (1, 3, 7, 4, 9) swapping since 9 > 4

Second Pass
(1, 3, 7, 4, 9) => (1, 3, 7, 4, 9) no swap since 3 > 1
(1, 3, 7, 4, 9) => (1, 3, 7, 4, 9) no swap since 7 > 3
(1, 3, 7, 4, 9) => (1, 3, 4, 7, 9) swapping since 7 > 4
(1, 3, 4, 7, 9) => (1, 3, 4, 7, 9) no swap since 9 > 7

Third Pass
(1, 3, 7, 4, 9) => (1, 3, 7, 4, 9) no swap
(1, 3, 4, 7, 9) => (1, 3, 4, 7, 9) no swap
(1, 3, 7, 4, 9) => (1, 3, 7, 4, 9) no swap
(1, 3, 4, 7, 9) => (1, 3, 4, 7, 9) no swap

The algorithm can be expressed as:

Complexity Analysis

Best Case Analysis

The best case to run the algorithm is against an array that it is already sorted. When the array is already sorted, the outer loop will run, making N-1 comparisons. Thus the lower asymptotic bound (which is the least amount of time needed by the algorithm) will be:

O(n)

Worst Case Analysis

The worst case to run is when we have N-1 passages through the outer loop. The inner loop starts at N-1 iterations and it is decreased by one per subsequent iteration of the outer loop. Thus we have:

(N-1) + (N-2) + (N-3)+...+ 1 =
\sum_{i=1}^{N-1}i =
N(N-1)/2

Thus the upper asymptotic bound (which is the most amount of time needed by the algorithm) will be:

O(N^{2})

Implementations

C Implementation

(Thank ThanosPloum for the implementation)

C# Implementation

Golang Implementation

Haskell Implementation

Java Implementation

JavaScript Implementation

Python Implementation

Advertisements