Bubble Sort

The algorithm is the most straightforward of all, but it’s also the least efficient. Every item is compared to every other item, with the order swapped until the larger items “bubble” to the top. The time complexity of this method is quadratic, and the amount of space required is constant.

The complexity of Space and Time

Best: O(n) time | O(1) space

Average: O(n^2) time | O(1) space

Worst: O(n^2) time | O(1) space

n is the length of the input array.

Input

[8, 5, 1, 9, 5, 6, 2]

Output

[1, 2, 5, 5, 6, 8, 9]

Hint

Every item is compared to every other item, with the order swapped until the larger items “bubble” to the top. 

Pseudo Code

DEFINE FUNCTION bubbleSort(array):
    SET isSorted TO False
    SET counter TO 0
    WHILE not isSorted:
        SET isSorted TO True
        FOR i IN range(len(array) - 1 - counter):
            IF array[i] > array[i + 1]:
                swap(i, i + 1, array)
                SET isSorted TO False
        counter += 1
    RETURN array

DEFINE FUNCTION swap(i, j, array):
    SET array[i], array[j] TO array[j], array[i]

Typescript Code

export function bubbleSort(array: number[]) {
  let isSorted = false;
  let counter = 0;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1 - counter; i++) {
      if (array[i] > array[i + 1]) {
        swap(i, i + 1, array);
        isSorted = false;
      }
    }
    counter++;
  }
  return array;
}

function swap(i: number, j: number, array: number[]) {
  const temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

mocha.setup("bdd");
describe("Bubble Sort", () => {
  it("Test Case #1", function () {
    const input = [8, 5, 1, 9, 5, 6, 2];
    chai.expect(bubbleSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]);
  });
  
  it("Test Case #2", function () {
    const input =[5, 3, 1, 2, 4];
    chai.expect(bubbleSort(input)).to.deep.equal([1,2,3,4,5]);
  });
});

mocha.run();

Demo

https://codepen.io/evalteam/pen/QWOWoKN