# Bubble Sort — But Make it Bridgerton

## JavaScript Algorithm Walkthrough

Algos, algos, algos! Fun stuff! And no, I am not being sarcastic, I very much enjoy this logic! Feel free to @ me when I hit binary trees and other data structures though, because I may be singing a different tune then. For now, I’m still working through easier algorithms so all is well in Shondaland!

Not unlike most of Regency era London high-society, bubble sort is amongst the most inefficient of algorithms. Its inefficient run time, O(n²), could be rivaled only by Daphne and Anthony Bridgerton’s inability to light a mere stove to heat their milk. You do NOT want the Bridgerton siblings in the kitchen any more than you’d want to use bubble sort for larger arrays (if you end up using it at all). Much like there are people better suited for the kitchen, there are algorithms better suited for sorting lists. Just had to get that out of the way before we go further.

The whole point of bubble sort is to compare each pair of adjacent values in an array. While iterating through the array, one must check each pair of numbers. If the first value is greater than the second, then you swap positions. The largest value is deposited furthest to the right following each iteration.

Bridgerton Breakdown: if we had an array of Featheringtons being presented before the queen to be sorted by societal status and Prudence unexpectedly takes a tumble, her societal status also plummets (she is now the Featherington of lowest value in comparison to her sisters).

let Featheringtons = ["Philipa","Prudence","Penelope"]if (Philipa > Prudence), then we will swap their positions.

When comparing the first two values of Philipa and Prudence, Prudence will have a lower value and will therefore switch places with Philipa, who managed to stay upright while greeting the queen. This will be the new array.

`let Featheringtons = ["Prudence", "Philipa","Penelope"]`

So to be clear, if we are sorting an array in ascending order, the algorithm will begin by comparing the first couple of values, Philipa and Prudence. Since Philipa has a higher status than Prudence, they will swap places, and Prudence is now at the front of the list — where we want our lowest values. We then move to the next pair, Philipa and Penelope. It will compare them and sort them accordingly and so on and so forth until the array is sorted.

Bridgerton Iteration: [**Philipa, Prudence**, Penelope] → [Prudence,** Philipa, Penelope**] → [Prudence, Penelope, Philipa]

Numerical Iteration: [**5,3**,4] → [3**,5,4**] → [3,4,5]

Now that we get the gist, let’s get into the nitty gritty.

`let array = [95, 31, 19, 7]`

function bubbleSort(arr){

let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])

let swapped

for(let i = arr.length; i > 0; i --){

swapped = false

for(let j = 0; j < i - 1; j++){

if(arr[j] > arr[j+1]){

swap(arr, j, j+1)

swapped = true

}

}

if(!swapped)break

}

return arr

}

- The first thing I like to do when writing out my bubble sort function is to immediately define a “swap” function to switch elements in an array. The swap function takes in 3 arguments: array, index1, and index2.

`let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])`

It will take the original order of index1 and index2 and switch them, as demonstrated above.

I chose to encapsulate my swap function in a variable within my bubble sort function, but you can also write a separate helper function to call inside your bubble sort function if that makes more sense to you.

2. Next, I create a *swapped *variable to use later in my code. This will be set to a boolean to check whether numbers have been swapped after completion of the inner loop.

3. Now we begin our outer for loop. This loop will iterate through the array **backwards**. We start at the end because, as previously mentioned, array[3] (last index of the array), is the position where our largest value, 95, will end up at the end of the first iteration of the inner loop. We initially set *swapped* to false. (We’ll come back to that later.)

`let array = [95, 31, 19, `**7**]

function bubbleSort(arr){

let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])

let swapped

**for(let i = arr.length; i > 0; i --){**

swapped = false

}

}

4. Next comes our inner loop, which iterates from the beginning of the array and is meant to compare each pair of values using a conditional statement. If currentElement > nextElement, we will call our handy swap function. Remember, Prudence made the queen grimace with displeasure and has the lowest value, so she gets swapped with her sister to the front of the array. Same applies here. Since a swap has been executed, we now update our *swapped* variable to true. In the example below, 95 and 31 will swap after the first iteration of the inner loop.

`let array = [`**95, 31**, 19, 7]

function bubbleSort(arr){

let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])

let swapped

for(let i = arr.length; i > 0; i --){

swapped = false

**for(let j = 0; j < i - 1; j++){**

if(arr[j] > arr[j+1]){

swap(arr, j, j+1)

swapped = true

}

}

}

return arr

}

5. Here is where we do our best to insert some efficiency into this dreadfully time complex algorithm by breaking out of the inner loop if the array is already sorted in ascending order. By checking *swapped* using the bang operator, we are saying if NOT *swapped*, break out of this inner loop. Remember that we only swap if currentEle > nextEle, so if this condition was never satisfied, it’s because the array is already sorted in ascending order. Therefore, we have no further need to loop and can break out of it.

`let array = [95, 31, 19, 7]`

function bubbleSort(arr){

let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])

let swapped

for(let i = arr.length; i > 0; i --){

swapped = false

for(let j = 0; j < i - 1; j++){

if(arr[j] > arr[j+1]){

swap(arr, j, j+1)

swapped = true

}

}

**if(!swapped)break**

}

**return arr**

}

Return the array outside the outer for loop to ensure all iterations are complete and you’re done!