A collection of sorting algorithms implemented in TypeScript for studying

SortingAlgorithm.ts

// - - Sorting Algorithms
// - Bubble Sort - O(n^2) - Quadratic Time
// - Merge Sort - O(n log n) - Quasilinear Time
// - Quick Sort - O(n log n) - Quasilinear Time
// - Heap Sort - O(n log n) - Quasilinear Time
// - Counting Sort - O(n + k) - where k is the range of the input integers
// - Radix Sort - O(d(n+k)) - where d is the number of digits in the input integers and k is the range of the input integers
// - Bucket Sort - O(n + k) - where k is the number of buckets used
// - insertion sort - O(n^2) - Quadratic Time
// - selection sort - O(n^2) - Quadratic Time

// - Small lists, any algorithm will do, but radix tends to do poorly in comparison to others due the overhead.
// - Medium lists, 60 to 1k, comparison sorts are good.
// - Large lists, Radix Sort!

//=========================- - Sorting Algorithms - -=========================//
namespace SortingAlgorithms {
  //- Bubble Sort - O(n^2) - Quadratic Time
  export function bubbleSort(arr: number[]) {
    let len = arr.length;

    let swapped;

    do {
      swapped = false;

      for (let i = 0; i < len - 1; i++) {
        if (arr[i] > arr[i + 1]) {
          let temp = arr[i];

          arr[i] = arr[i + 1];

          arr[i + 1] = temp;

          swapped = true;
        }
      }

      len--;
    } while (swapped);
    return arr;
  }

  //- Merge Sort - O(n log n) - Quasilinear Time
  export function mergeSort(arr: number[]) {
    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 merge(mergeSort(left), mergeSort(right));
  }

  function merge(left: number[], right: number[]) {
    const result: number[] = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
      const x = left[i] < right[j] ? left[i++] : right[j++]

      result.push(x)
    }

    return [...result, ... left.slice(i), ...right.slice(j)];
  }

  //- Quick Sort - O(n log n) - Quasilinear Time
  export function quickSort(arr: number[], left = 0, right = arr.length - 1) {
    if (left >= right) {
      return arr;
    }

    const index = partition(arr, left, right);

    quickSort(arr, left, index - 1);
    quickSort(arr, index, right);

    return arr;
  }

  function partition(arr: number[], left: number, right: number) {
    const pivotIndex = Math.floor((left + right) / 2);
    const pivot = arr[pivotIndex];

    while (left <= right) {
      while (arr[left] < pivot) {
        left++;
      }

      while (arr[right] > pivot) {
        right--;
      }

      if (left <= right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
      }
    }

    return left;
  }

  //- Heap Sort - O(n log n) - Quasilinear Time
  export function heapSort(arr: number[]) {
    const len = arr.length;

    // Build heap (rearrange array)
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
      heapify(len, i);
    }

    // One by one extract an element from heap
    for (let i = len - 1; i > 0; i--) {
      // Move current root to end
      [arr[0], arr[i]] = [arr[i], arr[0]];

      // call heapify on the reduced heap
      heapify(i, 0);
    }

    return arr;
  }

  const heapify = (len: number, i: number) => {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < len && arr[left] > arr[largest]) {
      largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
      largest = right;
    }

    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      heapify(len, largest);
    }
  };

  //- Counting Sort - O(n + k) - where k is the range of the input integers
  export function countingSort(arr: number[]) {
    const max = arr.reduce((acc, cur) => acc > cur ? acc : cur, 0); // Maximum element in the input array

    const count = new Array(max + 1).fill(0);
    const output = new Array(arr.length);

    // Count occurrences of each element in the input array
    for (let i = 0; i < arr.length; i++) {
      count[arr[i]]++;
    }

    // Compute prefix sum of the counts
    for (let i = 1; i < count.length; i++) {
      count[i] += count[i - 1];
    }

    // Sort the input array
    for (let i = arr.length - 1; i >= 0; i--) {
      output[count[arr[i]] - 1] = arr[i];
      count[arr[i]]--;
    }

    return output;
  }

  //- Radix Sort - O(d(n+k)) - where d is the number of digits in the input integers and k is the range of the input integers
  export function radixSort(arr: number[]) {
    const maxDigitCount = getMaxDigitCount(arr);

    let sortedArr = arr;

    for (let digit = 0; digit < maxDigitCount; digit++) {
      sortedArr = sortArrByDigit(sortedArr, digit);
    }

    return sortedArr;
  }

  function getMaxDigitCount(arr: number[]) {
    let maxDigitCount = 0;

    for (let num of arr) {
      maxDigitCount = Math.max(maxDigitCount, getDigitCount(num));
    }

    return maxDigitCount;
  }

  const getDigitCount = (num: number) => num === 0 ? 1 : Math.floor(Math.log10(Math.abs(num))) + 1

  function sortArrByDigit(arr: number[], digit: number) {
    const buckets: number[][] = Array.from({ length: 10 }, () => []);

    for (let num of arr) {
      const digitVal = getDigit(num, digit);

      buckets[digitVal].push(num);
    }

    return buckets.flat();
  }

  const getDigit = (num: number, digit: number) => Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10

  //- Bucket Sort - O(n + k) - where k is the number of buckets used
  export function bucketSort(arr: number[]) {
    if (arr.length === 0) {
      return arr;
    }

    // Determine minimum and maximum values in the array
    const [minValue, maxValue] = findMinMaxValues(arr);

    // Determine bucket size and number of buckets
    const bucketSize = determineBucketSize(maxValue, minValue);
    const bucketCount = determineBucketCount(maxValue, minValue, bucketSize);

    // Distribute array elements into buckets
    const buckets = distributeIntoBuckets(arr, bucketCount, bucketSize, minValue);

    // Sort buckets and concatenate into final sorted array
    return sortBuckets(buckets).flat();
  }

  function findMinMaxValues(arr: number[]) {
    let minValue = arr[0];
    let maxValue = arr[0];

    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
        minValue = arr[i];
      } else if (arr[i] > maxValue) {
        maxValue = arr[i];
      }
    }

    return [minValue, maxValue];
  }

  const determineBucketSize = (maxValue: number, minValue: number) => Math.floor((maxValue - minValue) / 10) + 1

  const determineBucketCount = (maxValue: number, minValue: number, bucketSize: number) => Math.floor((maxValue - minValue) / bucketSize) + 1

  function distributeIntoBuckets(arr: number[], bucketCount: number, bucketSize: number, minValue: number) {
    const buckets: number[][] = new Array(bucketCount).fill(null).map(() => []);

    for (let i = 0; i < arr.length; i++) {
      const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
      buckets[bucketIndex].push(arr[i]);
    }

    return buckets;
  }

  const sortBuckets = (buckets: number[][]) => buckets.map((bucket) => insertionSort(bucket))

  //- insertion sort - O(n^2) - Quadratic Time
  export function insertionSort(arr: number[]) {
    for (let i = 1; i < arr.length; i++) {
      const 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;
  }

  //- selection sort - O(n^2) - Quadratic Time
  export function selectionSort(arr: number[]): number[] {
    const len = arr.length;

    for (let i = 0; i < len; i++) {
      let minIndex = i;

      for (let j = i + 1; j < len; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }

      if (minIndex !== i) {
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
      }
    }

    return arr;
  }
}

const arr = [ 10, 23, 5234, 2, 14, 45435, 73, 3, 123, 0 ];

console.log(SortingAlgorithms.bubbleSort(arr));
console.log(SortingAlgorithms.mergeSort(arr));
console.log(SortingAlgorithms.quickSort(arr));
console.log(SortingAlgorithms.heapSort(arr));
console.log(SortingAlgorithms.countingSort(arr));
console.log(SortingAlgorithms.radixSort(arr));
console.log(SortingAlgorithms.bucketSort(arr));
console.log(SortingAlgorithms.insertionSort(arr));
console.log(SortingAlgorithms.selectionSort(arr));