JS Bubble Sort Algorithm
Tags: javascript, algorithms
Published: 2020-12-08 12:57:33

# TLDR

{% youtube _8NLC1rRKys %}

# The Problem

```javascript
// TODO: Sort this from highest to lowest w/o using any 'Array prototype stuff'

const nums = [52, 69, 15, 64, 62]; // Needs to be: [69, 64, 62, 52, 15]
```

## You Probably Shouldn't Read/Do This

**As this is about an algorithm, this is not actually how you would ever sort an _array._ You would use JS' built-in [sort](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort). So the 'real' solution for 👆🏾 would be: `nums.sort((a, b) => b - a)`**

## Stat By Sorting Just The First 2 Elements

Let's just focus on getting `[52, 69]` to `[69, 52]`. We will be as _imperative_ as possible, and manually type in every _index_ of this small array. As a quick reminder 🎗️, it emans that we will start with the first element - `52`, which is at _index `0`_ and proceed to the last element at _index `4`._

The procedure will be:

1. Confirm that 'index `0`' and 'index `1`' are indeed out of order. Is `[0]` `<` `[1]`. We could optionally check that both `[0]` and `[1]` are 'truth-y' - but we won't bother for now.
2. Keep a copy of `52` 'to the side' by _binding_ to a 'temp variable.'
3. Replace `52` - _'index `0`'' in the array_ -  with `69`. We will have 2 `69`s now.
4. Replace the original `69` - _'index `1`'_ -  with the 'temp value' `52` 👆🏾.

```javascript
// [52, 69, ...]
  if (nums[0] < nums[1]) {
    const sideValue = nums[0]; // 52
    nums[0] = nums[1]; // [69, 69, ...]
    nums[1] = sideValue; // [69, 52, ...]
  }
```

## Now, Let's Move Across the Whole Array - `[52, 69, 15, 64, 62]`

```javascript
// [..., 52, 15, ...] - this is already sorted ✅
  if (nums[1] < nums[2]) {
    const sideValue = nums[1];
    nums[1] = nums[2];
    nums[2] = sideValue;
  }

  // [..., 15, 64, ...]
  if (nums[2] < nums[3]) {
    const sideValue = nums[2]; // 15
    nums[2] = nums[3]; // [..., 64, 64, ...]
    nums[3] = sideValue; // [..., 64, 15, ...]
  }

  // [..., 15, 62]
  if (nums[3] < nums[4]) {
    const sideValue = nums[3]; // 15
    nums[3] = nums[4]; // [..., 62, 62]
    nums[4] = sideValue; // [..., 62, 15]
  }
```

The results: `[52, 69, 64, 62, 15]`

So...it's working...but we have to go back to the front of the array and keep checking it _until_ there are no elements that are 'out of order.' 

Yup...that's a _➿._ A `do`-`while` ➿. Again, for clarity, we will just keep the 'manual _indices._'

## `do`-`while` 🎼

A `do`-`while` is rarely used, but the concept is that the `do` part insures at least 1 _iteration_ of the loop. If you've never used b4, kindly [review the example here](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/do...while) b4 proceeding.

This time, we will keep a _boolean_ called `isOutOfOrder`. This will stay as `true` _until..._ it's not 🙄. This will be used in our `while` to finally exit the ➿.

Along the way, we will use `else` to check each 'pair of numbers' one at a time, with a final `else` condition to set `isOutOfOrder = false`.

```javascript
let isOutOfOrder = true;

do {
  console.log(nums);

  // [52, 69, ...]
  if (nums[0] < nums[1]) {
    const sideValue = nums[0]; // 52
    nums[0] = nums[1]; // [69, 69, ...]
    nums[1] = sideValue; // [69, 52, ...]
  }

  // [..., 52, 15, ...]
  else if (nums[1] < nums[2]) {
    const sideValue = nums[1];
    nums[1] = nums[2];
    nums[2] = sideValue;
  }

  // [..., 15, 64, ...]
  else if (nums[2] < nums[3]) {
    const sideValue = nums[2]; // 15
    nums[2] = nums[3]; // [..., 64, 64, ...]
    nums[3] = sideValue; // [..., 64, 15, ...]
  }

  // [..., 15, 62]
  else if (nums[3] < nums[4]) {
    const sideValue = nums[3]; // 15
    nums[3] = nums[4]; // [..., 62, 62]
    nums[4] = sideValue; // [..., 62, 15]
  } else {
    isOutOfOrder = false;
  }
} while (isOutOfOrder);

console.log(nums);
```

This time, the results are good 🤓!

```bash
[ 52, 69, 15, 64, 62 ]
[ 69, 52, 15, 64, 62 ]
[ 69, 52, 64, 15, 62 ]
[ 69, 64, 52, 15, 62 ]
[ 69, 64, 52, 62, 15 ]
[ 69, 64, 62, 52, 15 ]
[ 69, 64, 62, 52, 15 ]
```

## function `bubbleSort`

We accomplished our task...sort of. Obviously 🙄, we cannot just manually type in all of the _indices._ We need to wrap everything up in some sort of loop that proceeds all the way through the _array._ So, here is an 'official' `bubbleSort` _function._

You will notice a few minor differences, but the logic is largely the same. The most significant difference is that the _boolean_ is checking if 'sorting is complete' rather than if there is anything 'out of order.' In this way, you can hopefully see both approaches.

```javascript
function bubbleSort(stuffToSortOut) {
  // Could start by assuming 'false' 🤷🏾‍♂️
  let swapped;
  do {
    swapped = false;
    // Keep 🏃🏾‍♂️ this thing across all of the indexes in the stuffToSortOut
    for (let i = 0; stuffToSortOut.length > 0; i++) {
      /**
       * IF the current element and the next element are both 'truthy' AND
       * IF the current element is LESS THAN the next element
       */
      if (stuffToSortOut[i] && stuffToSortOut[i + 1] && stuffToSortOut[i] < stuffToSortOut[i + 1]) {
        // Put the current value 'to the side'
        const temp = stuffToSortOut[i];

        // Replace the current element with the value from the next element
        stuffToSortOut[i] = stuffToSortOut[i + 1];

        // Replace the next element with the 'side value' 👆🏾
        stuffToSortOut[i + 1] = temp;
        swapped = true;
      }
    }
  } while (
    // Are we done yet? If not, go back and do it again!
    swapped
  );

  return stuffToSortOut;
}
```

And...the results are the same: `[69, 64, 62, 52, 15]`

## The Gist

{% gist https://gist.github.com/manavm1990/14a2072f3935719ceaee55268b32c158 %}

## Consider Building a Practical Application Instead of This 💩

Again, there is no need to actually do all of this bologna. It is just an intellectual exercise to better understand programming...and _some_ employers might ask you to 'white board' something like this 🤷🏾‍♂️.