Bubble and Selection and Insertion!

Sorting is a very common thing to do in Software Engineering. Data needs to get organized! You wouldn’t just toss a file randomly inside your cabinets, would you? No, of course you wouldn’t. And if you answered differently, shame on you. This blog entry is going to be comparing some of the most common sorting methods I’ve seen when practicing algorithms. Before we start, though. I want to talk about VisuAlgo. This amazing website helps me visualize algorithm solutions and it’s a really good tool for me to understand how to go about solving problems. They even include some pseudocode that gets highlighted in real-time depending on what step the method is currently in. I’ve included animated graphs below to show you how they help!

Bubble Sort

Fun name! Just as the name implies, the largest value in the array “bubbles” to the end of the array. The array gets iterated over as adjacent elements get compared and switch places accordingly, that is if the currently selected element has a higher value than the element after it, they switch. The entire array is looped over continuously until it is completely sorted.

Bubble Sort

Here’s a sample of a Bubble Sort function using ES2015 syntax.

function bubbleSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr
}

We build a helper function called swap within in order to, well, swap the elements should the if conditional be met within those nested loops.

Selection Sort

Selection sort works by having the method select the lowest value in an array through each loop and then moving it to the front of the array. Then, we move up to the next element in place and do another loop, finding the newest minimum value and moving that to the front of the array until eventually it gets sorted.

Selection Sort

Here’s a sample of a Selection Sort function using ES2015 syntax.

function selectionSort(arr) {   const swap = (arr, idx1, idx2) =>      ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);
for (let i = 0; i < arr.length; i++) { let lowest = i; for (let j = 1; j < arr.length; j++) { if (arr[lowest] > arr[j]) { lowest = j; } } if (i !== lowest) { swap(arr, i, lowest); } } return arr;}

We get the same swap helper function to switch out the values. We set an initial lowest value and then loop and compare each value to the lowest one. Once the loops ends, send the value to the front.

Insertion Sort

Insertion sort slowly builds the sorted array over time by grabbing the necessary value and comparing it to each value before it to see if it should move. This is similar to how we would usually do it by hand.

Here’s a sample of an Insertion Sort function. No ES2015 syntax this time, though!

function insertionSort(arr) {   for (let i = 1; i < arr.length; i++) {      let currentVal = arr[i]      for (let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {         arr[j + 1] = arr[j]      }   arr[j + 1] = currentVal   }return arr}

So we get the second value in the array first to compare it to the first value to see if it needs to switch. Then, currentVal keeps getting re-defined depending on what iteration i is on and how many elements have been sorted already, which we then eventually return the whole array.

Software engineer