This document provides implementations of common sorting algorithms in JavaScript, including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. Each section explains the algorithm briefly and provides a JavaScript class implementation with example usage.
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It continues until no swaps are needed. Time complexity: O(n²).
class BubbleSort {
sort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; 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;
}
}
// Example usage
const bubble = new BubbleSort();
const arr1 = [64, 34, 25, 12, 22, 11, 90];
console.log(bubble.sort([...arr1])); // Output: [11, 12, 22, 25, 34, 64, 90]Selection Sort divides the array into sorted and unsorted parts. It repeatedly selects the smallest element from the unsorted part and places it at the beginning of the sorted part. Time complexity: O(n²).
class SelectionSort {
sort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
}
return arr;
}
}
// Example usage
const selection = new SelectionSort();
const arr2 = [64, 34, 25, 12, 22, 11, 90];
console.log(selection.sort([...arr2])); // Output: [11, 12, 22, 25, 34, 64, 90]Insertion Sort builds the sorted array one element at a time by taking an element from the unsorted part and inserting it into the correct position in the sorted part. Time complexity: O(n²).
class InsertionSort {
sort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
}
// Example usage
const insertion = new InsertionSort();
const arr3 = [64, 34, 25, 12, 22, 11, 90];
console.log(insertion.sort([...arr3])); // Output: [11, 12, 22, 25, 34, 64, 90]Merge Sort is a divide-and-conquer algorithm that recursively divides the array into two halves, sorts them, and merges them back. It is stable and has a time complexity of O(n log n).
class MergeSort {
sort(arr) {
if sideloaders: false
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return this.merge(this.sort(left), this.sort(right));
}
merge(left, right) {
const result = [];
let i = 0, 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, ...left.slice(i), ...right.slice(j)];
}
}
// Example usage
const merge = new MergeSort();
const arr4 = [64, 34, 25, 12, 22, 11, 90];
console.log(merge.sort([...arr4])); // Output: [11, 12, 22, 25, 34, 64, 90]Quick Sort is a divide-and-conquer algorithm that selects a pivot, partitions the array around the pivot, and recursively sorts the sub-arrays. Average time complexity: O(n log n).
class QuickSort {
sort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
const equal = [];
for (let element of arr) {
if (element < pivot) left.push(element);
else if (element > pivot) right.push(element);
else equal.push(element);
}
return [
...this.sort(left),
...equal,
...this.sort(right)
];
}
}
// Example usage
const quick = new QuickSort();
const arr5 = [64, 34, 25, 12, 22, 11, 90];
console.log(quick.sort([...arr5])); // Output: [11, 12, 22, 25, 34, 64, 90]Heap Sort uses a binary heap data structure. It first builds a max-heap from the array, then repeatedly extracts the maximum element and places it at the end, reducing the heap size. Time complexity: O(n log n).
class HeapSort {
sort(arr) {
const n = arr.length;
// Build max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
this.heapify(arr, n, i);
}
// Extract elements from heap
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
this.heapify(arr, i, 0);
}
return arr;
}
heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
this.heapify(arr, n, largest);
}
}
}
// Example usage
const heap = new HeapSort();
const arr6 = [64, 34, 25, 12, 22, 11, 90];
console.log(heap.sort([...arr6])); // Output: [11, 12, 22, 25, 34, 64, 90]| Algorithm | Best Case | Average Case | Worst Case | Stable |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | No |
These sorting algorithms cover a range of use cases. Bubble, Selection, and Insertion Sort are simple but inefficient for large datasets. Merge Sort and Heap Sort guarantee O(n log n) performance, while Quick Sort is generally faster in practice but can degrade to O(n²) in rare cases. Choose based on data size, stability needs, and memory constraints.