JavaScript Algorithms: Bubble Sort

Bubble sort is a simple algorithm for sorting, but it’s also quite inefficient, as its worst case is O(n^2) complexity.

But it’s worth learning about it.

We loop through an array, and we keep comparing one item to the one right n…

Bubble sort is a simple algorithm for sorting, but it’s also quite inefficient, as its worst case is O(n^2) complexity.

But it’s worth learning about it.

We loop through an array, and we keep comparing one item to the one right next to it.

If the item on the right is smaller, we swap the two positions.

Here’s our implementation:

const bubbleSort = (originalArray) => {
  let swapped = false

  const a = [...originalArray]

  for (let i = 1; i < a.length - 1; i++) {
    swapped = false

    for (let j = 0; j < a.length - i; j++) {
      if (a[j + 1] < a[j]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }

    if (!swapped) {
      return a
    }
  }

  return a
}

You can see the O(n^2) comes from the fact we are looping the array 2 times, to check if we need to swap the item with the one on the right.

We start with the first element, and we compare it with the second. If the first is bigger, we swap them. Otherwise we leave it as-is, and we switch to the second element of the array. We compare it with the third. Again, if the 2nd is bigger than the 3rd, we swap them, and we continue swapping until it finds its position in the array.

Here’s an example:

Suppose we run bubbleSort([2, 1, 3]).

First we compare 2 with 1. 2 is > 1, so we swap them:

1 2 3

then we compare 2 with 3. 2 < 3, so we leave it as-is. We skip the last element, since we know that due to our workflow, it’s always going to be the biggest element.


Print Share Comment Cite Upload Translate
APA
flaviocopes.com | Sciencx (2024-03-28T15:48:40+00:00) » JavaScript Algorithms: Bubble Sort. Retrieved from https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/.
MLA
" » JavaScript Algorithms: Bubble Sort." flaviocopes.com | Sciencx - Wednesday November 25, 2020, https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/
HARVARD
flaviocopes.com | Sciencx Wednesday November 25, 2020 » JavaScript Algorithms: Bubble Sort., viewed 2024-03-28T15:48:40+00:00,<https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/>
VANCOUVER
flaviocopes.com | Sciencx - » JavaScript Algorithms: Bubble Sort. [Internet]. [Accessed 2024-03-28T15:48:40+00:00]. Available from: https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/
CHICAGO
" » JavaScript Algorithms: Bubble Sort." flaviocopes.com | Sciencx - Accessed 2024-03-28T15:48:40+00:00. https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/
IEEE
" » JavaScript Algorithms: Bubble Sort." flaviocopes.com | Sciencx [Online]. Available: https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/. [Accessed: 2024-03-28T15:48:40+00:00]
rf:citation
» JavaScript Algorithms: Bubble Sort | flaviocopes.com | Sciencx | https://www.scien.cx/2020/11/25/javascript-algorithms-bubble-sort/ | 2024-03-28T15:48:40+00:00
https://github.com/addpipe/simple-recorderjs-demo