HomeOur TeamContact
Sorting
Bubble Sort
Nisar
Nisar
January 26, 2022
1 min

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


Tags

Previous Article
Multi String Search
Next Article
Insertion Sort
Nisar

Nisar

Related Posts

Heap Sort
January 31, 2022
1 min
© 2022, All Rights Reserved.

Quick Links

Advertise with usAbout UsContact Us

Social Media