Algorithms in JavaScript: Part 2
In this second part of the Algorithms in JavaScript series, we are going to look at some common sorting algorithms, in particular we are going to see the Bubble sort, the Quick sort and the Merge sort.
While as an extra step we may easily create a custom comparison function to sort complex data structures and not just numbers, that wouldn't impact the main logic of the sorting algorithm and would just add noise. So let's make a couple of assumptions to focus solely on the algorithm and simplify:
- the input array contains only numbers;
- the sorting is always in ascendant order.
Bubble sort
The Bubble sort algorithm is a simple sorting algorithm that repeatedly steps through the elements of the array, compares the adjacent elements and then swaps them in case they are in the wrong order. It repeats the process until the list is fully sorted (it doesn't make a single change in a full scan).
// Input containing edge cases like duplicates and negative numbers.
const unorderedArray = [2, 5, 6, 1, 4, 3.9, 10.5, 10, 3, 0 ,-4, -2.9, -3, 0, 2, 4];
//BUBBLE SORT
function bubbleSort(inputArray) {
let isChanged = true;
while(isChanged) {
isChanged = false;
for(let i=0; i<inputArray.length-1; i++) {
if(inputArray[i] > inputArray[i+1]){
swap(i, i+1);
isChanged = true;
}
}
}
return inputArray;
function swap(index1, index2){
const swapNumber = inputArray[index1];
inputArray[index1] = inputArray[index2];
inputArray[index2] = swapNumber;
}
}
console.log(bubbleSort(unorderedArray)); //[ -4, -3, -2.9, 0, 0, 1, 2, 2, 3, 3.9, 4, 4, 5, 6, 10, 10.5 ]
Quick sort (the one I prefer)
The Quick sort algorithm is the one that I prefer for readability, ease of understanding and speed. In fact, although the speed of a sorting algorithm in a real-life case largely depends upon the inputs you are working with, Quick sort has proved to have the best performance in the average case (for most inputs).
The algorithm is quite easy, you take a pivot point (remove an element) from your array, then separate in two sub-arrays all the numbers that are greater or smaller than the pivot number. Then you recursively Quick sort those sub-arrays. Near the end of the recursion depth (exactly at the end -1 step, as the end is the exit case that just return the single number) you are left with single numbers, and you can easily order them inserting them before (if less than) and after (if greater than) the pivot number. So you know that that small array of 2/3 elements is ordered. You also know that the step you are receiving back from the recursion is not only ordered, but also that all the numbers there contained are less than your pivot point (you filtered them before entering the recursion), so you are left with: a series of ordered numbers smaller that the pivot, the pivot, a series of ordered numbers greater than the pivot. You can then just concat them ending with an ordered series. Let the algorithm repeat itself for all the recursion steps and you'll end up with the full array completely sorted.
// Input containing edge cases like duplicates and negative numbers.
const unorderedArray = [2, 5, 6, 1, 4, 3.9, 10.5, 10, 3, 0 ,-4, -2.9, -3, 0, 2, 4];
function quickSort(inputArray) {
if(inputArray.length < 2) {
return inputArray;
}
const pivotNumber = inputArray.pop();
const leftBranch = [];
const rightBranch = [];
inputArray.forEach(element => {
if(element < pivotNumber) {
leftBranch.push(element);
} else {
rightBranch.push(element);
}
});
return [...quickSort(leftBranch), pivotNumber, ...quickSort(rightBranch)];
}
console.log(quickSort(unorderedArray)); //[ -4, -3, -2.9, 0, 0, 1, 2, 2, 3, 3.9, 4, 4, 5, 6, 10, 10.5 ]
Merge sort
The Merge sort algorithm is based as the Quick sort on recursion and uses a divide-and-conquer approach. It breaks the main array into two sub-arrays from the middle point, then recursively Merge sort them. It goes this way until it reaches single numbers, then combines and orders them. When coming back from the recursion steps, it knows that it has 2 ordered sub-arrays, so that it can concat them and see if there are values to change at the merging point. If there are it swaps the elements forward until it reaches the end of the array or a greater number (right position, no need to swap more). At this point it still has two ordered sub-arrays, and the merging point (the point where the two known ordered parts are connected) has "moved closer to the beginning of the array". It then continues to move merging point values in the right places until the merging point is the beginning of the series or the values at the merging point need no swaps, ending with the fully sorted array.
// Input containing edge cases like duplicates and negative numbers.
const unorderedArray = [2, 5, 6, 1, 4, 3.9, 10.5, 10, 3, 0 ,-4, -2.9, -3, 0, 2, 4];
//MERGE SORT
function mergeSort(inputArray) {
if(inputArray.length < 2) {
return inputArray;
}
const halfPoint = Math.round(inputArray.length / 2);
const leftBranch = mergeSort(inputArray.splice(0, halfPoint));
const rightBranch = mergeSort(inputArray);
const result = [...leftBranch, ...rightBranch];
for(let i=halfPoint-1; i>-1; i--){
if(result[i] < result[i+1]){
break; //we know the whole array is sorted
}
for(let j=i; j<result.length-1; j++){
if(result[j] < result[j+1]) {
break; //we know the whole part after `i` is sorted
}
swap(result, j, j+1);
}
}
return result;
function swap(array, index1, index2){
const swapNumber = array[index1];
array[index1] = array[index2];
array[index2] = swapNumber;
// FYI NOTE: there is also the modern ES6+ way (through destructuring assignment we can achieve a swap in place)
// [array[index1], array[index2]] = [array[index2], array[index1]];
}
}
console.log(mergeSort([unorderedArray])); //[ -4, -3, -2.9, 0, 0, 1, 2, 2, 3, 3.9, 4, 4, 5, 6, 10, 10.5 ]
For updates, insights or suggestions, feel free to post a comment below! 
