Sorting Algorithms in JS
Implementation and performance comparisons of sorting algorithms like Bubble, Selection, Insertion, Merge, Quick, and Radix in JavaScript.
Sorting algorithms are among the most encountered algorithms in the programming world. While this topic is not specific to JavaScript, it is important to know how algorithms are written, compare their performance, and know when to use which algorithm.
Bubble Sort
It sorts by comparing 2 elements, moving the largest element to the end each time. It has a worst-case complexity of O(n^2).
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}We can optimize this function a bit. If no swaps are made in a loop, the sorting is done. In this case, we can terminate the loop.
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}We can optimize it further. Since we move the largest element to the end each time, there is no need to check the last element in the next iteration. In this case, we can reduce the loop by one element.
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}Selection Sort
It finds the smallest element in the array and swaps it with the first element. Then, it finds the smallest among the remaining elements and swaps it with the second element. This process continues until the end of the array. It has a worst-case complexity of O(n^2).
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}Insertion Sort
It considers the first element of the array as sorted. Then, it inserts the next element into the appropriate place in the sorted part. This process continues until the end of the array. It has a worst-case complexity of O(n^2).
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}Merge Sort
We can say that the algorithms we have seen so far no longer have a place in the modern world. Merge sort is a more optimized algorithm. It divides the array in half, sorts each half, and then merges the two sorted halves. It has a worst-case complexity of O(n log n).
// First, let's write a function that merges two sorted arrays
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}The disadvantage of this sorting algorithm is that it creates a new array and call stack each time. This can lead to memory consumption in large arrays.
Quick Sort
It is a fast algorithm like Merge Sort. It selects an element of the array as the pivot and places elements smaller than the pivot to its left, and larger ones to its right. Then, it sorts each part separately. It has a worst-case complexity of O(n^2).
function pivot(arr, start = 0, end = arr.length - 1) {
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
let pivot = arr[start];
let swapIndex = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIndex++;
swap(arr, swapIndex, i);
}
}
swap(arr, start, swapIndex);
return swapIndex;
}
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
let pivotIndex = pivot(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}Radix Sort
This algorithm is used to sort integer numbers. It sorts the numbers according to their digits. It has a worst-case complexity of O(nk), where k is the number of digits.
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(arr) {
let maxDigits = 0;
for (let i = 0; i < arr.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(arr[i]));
}
return maxDigits;
}
function radixSort(arr) {
const maxDigitCount = mostDigits(arr);
for (let k = 0; k < maxDigitCount; k++) {
let digitBuckets = Array.from({ length: 10 }, () => []);
for (let i = 0; i < arr.length; i++) {
let digit = getDigit(arr[i], k);
digitBuckets[digit].push(arr[i]);
}
arr = [].concat(...digitBuckets);
}
return arr;
}More Advanced Sorting Algorithms
In addition to the algorithms given above, there are more advanced algorithms. Some of these algorithms are:
- Heap Sort
- Shell Sort
- Counting Sort
- Bucket Sort
- Tim Sort
- Quick Sort (3-way)
Performance Comparison
Each sorting algorithm has its advantages and disadvantages. It is important to know when to use which algorithm. In the modern world, the most commonly used algorithms are Merge Sort and Quick Sort. When using JavaScript, you can always use the built-in Array.prototype.sort function. This function uses an algorithm optimized by browsers and Node.js. It is important to choose the most suitable algorithm for each case rather than sticking to a single algorithm.