JS Bubble Sort Algorithm

TLDR

The Problem

// 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. 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 69s now.
4. Replace the original 69 - 'index 1' - with the 'temp value' 52 👆🏾.

// [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]

// [..., 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 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.

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 🤓!

[ 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.

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

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 🤷🏾‍♂️.