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

# .css-10kjd3a{box-sizing:border-box;margin:0;min-width:0;display:block;color:var(--theme-ui-colors-heading,#2d3748);font-weight:900;-webkit-text-decoration:none;text-decoration:none;margin-bottom:1rem;font-size:1.875rem;position:relative;}@media screen and (min-width:640px){.css-10kjd3a{font-size:2.25rem;}}@media screen and (min-width:1024px){.css-10kjd3a{font-size:3rem;}}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

Heap Sort
January 31, 2022
1 min