Why always me?1. Bubble Sort
Performance:
- Best: ( O(n) )
- Average: ( O(n^2) )
- Worst: ( O(n^2) )
Memory: ( O(1) )
Pros:
- Simple to implement
Cons:
- Inefficient for large datasets
( n ) Derivation:
- ( n ) represents the number of elements to be sorted. The algorithm compares each pair of adjacent elements, making it quadratic in the worst case.
// JavaScript implementation of Bubble Sort
function bubbleSort(arr: number[]): number[] {
const n = arr.length;
let swapped = false;
for (let i = 0; i < n - 1; i++) {
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;
}
bubbleSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]2. Selection Sort
Performance:
- Best: ( O(n^2) )
- Average: ( O(n^2) )
- Worst: ( O(n^2) )
Memory: ( O(1) )
Pros:
- Simple and predictable performance
Cons:
- Inefficient for large datasets
( n ) Derivation:
- It iteratively finds the minimum element from the unsorted section and puts it at the beginning, making the time complexity quadratic.
// JavaScript implementation of Selection Sort
function selectionSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex !== i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
selectionSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]3. Insertion Sort
Performance:
- Best: ( O(n) )
- Average: ( O(n^2) )
- Worst: ( O(n^2) )
Memory: ( O(1) )
Pros:
- Efficient for nearly sorted lists
Cons:
- Inefficient for large or reverse-sorted datasets
( n ) Derivation:
- ( n ) is the number of elements. It builds a sorted array one element at a time, making it quadratic in the worst case.
// JavaScript implementation of Insertion Sort
function insertionSort(arr: number[]): number[] {
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;
}
insertionSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]4. Merge Sort
Performance:
- Best: ( O(n \log n) )
- Average: ( O(n \log n) )
- Worst: ( O(n \log n) )
Memory: ( O(n) )
Pros:
- Stable and has consistent performance
Cons:
- Requires additional memory space
( n ) Derivation:
- The array is recursively divided in half, and each half is sorted. Since the algorithm divides and then merges, it’s ( O(n \log n) ).
// JavaScript implementation of Merge Sort
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
function merge(left: number[], right: number[]): number[] {
const sorted = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) sorted.push(left[i++]);
else sorted.push(right[j++]);
}
return sorted.concat(left.slice(i)).concat(right.slice(j));
}
}
mergeSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]5. Quick Sort
Performance:
- Best: ( O(n \log n) )
- Average: ( O(n \log n) )
- Worst: ( O(n^2) )
Memory: ( O(\log n) ) (average)
Pros:
- Fast and doesn’t require additional space
Cons:
- Performance depends on pivot selection; worst case is rare but possible
( n ) Derivation:
- It partitions the array and then recursively sorts the partitions. The choice of pivot affects whether the partitioning is balanced.
// JavaScript implementation of Quick Sort
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) left.push(arr[i]);
else if (arr[i] > pivot) right.push(arr[i]);
}
return quickSort(left).concat(pivot, quickSort(right));
}
quickSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]6. Heap Sort
Performance:
- Best: ( O(n \log n) )
- Average: ( O(n \log n) )
- Worst: ( O(n \log n) )
Memory: ( O(1) )
Pros:
- Consistent performance and in-place
Cons:
- Somewhat slower compared to well-implemented Quick Sort
( n ) Derivation:
- It uses a binary heap data structure, and the time complexity arises from repeatedly removing the maximum element and then maintaining the heap property.
// JavaScript implementation of Heap Sort
function heapSort(arr: number[]): number[] {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
function heapify(arr: number[], n: number, i: number): void {
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]];
heapify(arr, n, largest);
}
}
}
heapSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]7. Counting Sort
Performance:
- Best: ( O(n + k) )
- Average: ( O(n + k) )
- Worst: ( O(n + k) )
Memory: ( O(k) )
Pros:
- Efficient for small ranges of integer keys
Cons:
- Not suitable for sorting elements with non-integer keys or large ranges
( n ) Derivation:
- ( n ) is the number of elements, and ( k ) is the range of the input. It counts the occurrence of each element.
Each algorithm’s performance is affected by the number of elements ( n ) being sorted and other factors like the range of values ( k ) or the choice of pivot.
// JavaScript implementation of Counting Sort
function countingSort(arr: number[]): number[] {
const n = arr.length;
const max = Math.max(...arr);
const count = Array(max + 1).fill(0);
const output = Array(n);
for (let i = 0; i < n; i++) count[arr[i]]++;
for (let i = 1; i <= max; i++) count[i] += count[i - 1];
for (let i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return output;
}
countingSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]8. Radix Sort
Performance:
- Best: ( O(nk) )
- Average: ( O(nk) )
- Worst: ( O(nk) )
Memory: ( O(n + k) )
Pros:
- Efficient for sorting integers with a fixed number of digits
Cons:
- Not suitable for floating-point numbers or negative integers
( n ) Derivation:
- ( n ) is the number of elements, and ( k ) is the number of digits in the largest element. It sorts the elements by their individual digits.
// JavaScript implementation of Radix Sort
function radixSort(arr: number[]): number[] {
const max = Math.max(...arr);
const maxDigits = max.toString().length;
for (let i = 0; i < maxDigits; i++) {
const buckets = Array.from({ length: 10 }, () => []);
for (let j = 0; j < arr.length; j++) {
const digit = Math.floor(arr[j] / 10 ** i) % 10;
buckets[digit].push(arr[j]);
}
arr = buckets.flat();
}
return arr;
}
radixSort([5, 3, 8, 4, 2]); // Output: [2, 3, 4, 5, 8]Genrify Sorts
function bubbleSort<T>(arr: T[], compareFn: (a: T, b: T) => number): T[] {
const len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (compareFn(arr[j], arr[j + 1]) > 0) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
function selectionSort<T>(arr: T[], compareFn: (a: T, b: T) => number): T[] {
const len = arr.length;
for (let i = 0; i < len; i++) {
let minIdx = i;
for (let j = i + 1; j < len; j++) {
if (compareFn(arr[j], arr[minIdx]) < 0) {
minIdx = j;
}
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}
function insertionSort<T>(arr: T[], compareFn: (a: T, b: T) => number): T[] {
const len = arr.length;
for (let i = 1; i < len; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && compareFn(arr[j], key) > 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return arr;
}