Bubble Sort

Bubble Sort#

Bubble sort involves swaping elements to sort an array from lowest to highest.

This is the easiest sorting algorithm to implement (and understand).

Time Complexity#

Each value is iterated through the sum of N times.

\[O(n^2)\]

Simple Proof#

Reminder that the sum of a linear series of values is

\[ \begin{align}\begin{aligned}100 + 1 = 101\\99 + 2 = 101\\..\\98 + 3 = 101\end{aligned}\end{align} \]

or more abstractly. Where the last element will be 1

\[ \begin{align}\begin{aligned}N\\N-1\\N-2\\..\\N-N+1 = 1\end{aligned}\end{align} \]

or more simply put

\[\displaystyle\sum_{i=0}^n {N - i}\]

Thus, assuming the worst case of a reversed list where \(N+N-1\) is the last value, we get

\[{n^2 - n} \over 2\]

giving a running time of

\[O(n^2)\]

Implementation#

Pseudo-code

FOR i FROM length of array DOWNTO 2 DO
 FOR j FROM 0 TO i - 1 DO
   IF arr[j] > arr[j + 1] THEN
     k = arr[j + 1]
     arr[j + 1] = arr[j]
     arr[j] = k
   END IF
 END FOR
END FOR

Typescript

for (let i = array.length - 1; i > 1; i--) {
  for (let j = 0; j < i; j++) {
    if (array[j] > array[j+1]) {
      const k = array[j+1]
      array[j+1] = array[j]
      array[j] = k
    }
  }
}

C++

for (int i = arrayLength - 1; i > 1; i--) {
  for (int j = 0; j < i; j++) {
    if (array[j] > array[j+1]) {
      int k = array[j+1];
      array[j+1] = array[j];
      array[j] = k;
    }
  }
}
Contents