Some Common Sorting Algorithms

https://www.freecodecamp.org/news/sorting-algorithms-explained-with-examples-in-python-java-and-c/

Selection sort

Selection Sort is one of the simplest sorting algorithms. This algorithm gets its name from the way it iterates through the array: it selects the current smallest element, and swaps it into place.

typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
export const SelectionSort = (nums: number[]) => {
  for (let i = 0; i < nums.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      // eslint-disable-next-line no-param-reassign
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }
  return nums;
};

Bubble sort

Just like the way bubbles rise from the bottom of a glass, bubble sort is a simple algorithm that sorts a list, allowing either lower or higher values to bubble up to the top. The algorithm traverses a list and compares adjacent values, swapping them if they are not in the correct order.

With a worst-case complexity of O(n^2), bubble sort is very slow compared to other sorting algorithms like quicksort. The upside is that it is one of the easiest sorting algorithms to understand and code from scratch.

From technical perspective, bubble sort is reasonable for sorting small-sized arrays or specially when executing sort algorithms on computers with remarkably limited memory resources.

typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
export const BubbleSort = (array: number[]) => {
  let sorted = false;
  while (!sorted) {
    sorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        sorted = false;
        // eslint-disable-next-line no-param-reassign
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
      }
    }
  }
  return array;
};

Insertion sort

Compare the key element with the previous elements. If the previous elements are greater than the key element, then you move the previous element to the next position.

typescript
1
2
3
4
5
6
7
8
9
10
11
export const InsertionSort = (arr: number[]) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        // eslint-disable-next-line no-param-reassign
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      }
    }
  }
  return arr;
};

Quick sort

Quick sort is an efficient divide and conquer sorting algorithm. Average case time complexity of Quick Sort is O(nlog(n)) with worst case time complexity being O(n^2) depending on the selection of the pivot element, which divides the current array into two sub arrays.

The steps involved in Quick Sort are:

  • Choose an element to serve as a pivot, in this case, the last element of the array is the pivot.
  • Partitioning: Sort the array in such a manner that all elements less than the pivot are to the left, and all elements greater than the pivot are to the right.
  • Call Quicksort recursively, taking into account the previous pivot to properly subdivide the left and right arrays. (A more detailed explanation can be found in the comments below)
typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Divide and Conquer
export const QuickSort = (array: number[]) => {
  if (array.length <= 1) return array;
  const pivot = array[array.length - 1];
  const left = [];
  const right = [];
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }
  return [...QuickSort(left), pivot, ...QuickSort(right)];
};

Heap sort

https://www.geeksforgeeks.org/heap-sort/

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.

  • Heap sort is an in-place algorithm.
  • Its typical implementation is not stable, but can be made stable (See this)
  • Typically 2-3 times slower than well-implemented QuickSort.  The reason for slowness is a lack of locality of reference.
typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @description 堆排序
 * @param arr - 待排序数组
 * @param i - index of the element to be heapified
 * @param len - size of the heap
 * @summary The heap sort algorithm consists of two phases. In the first phase the array is converted into a max heap. And in the second phase the highest element is removed (i.e., the one at the tree root) and the remaining elements are used to create a new max heap.
 */
export const heapify = (arr: number[], i: number, len: number) => {
  let largest = i;
  // left child
  const left = 2 * i + 1;
  // right child
  const right = 2 * i + 2;
  // compare left child with root, if left child is larger than root, then largest is left child
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  // compare right child with root, if right child is larger than root, then largest is right child
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  // if largest is not root, swap and continue heapifying
  if (largest !== i) {
    // eslint-disable-next-line no-param-reassign
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, largest, len);
  }
};

export const HeapSort = (arr: number[]) => {
  const len = arr.length;
  // build heap
  // `floor(len / 2)` doesn't mean the middle of the tree, but the number of nodes that aren't leaves.
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(arr, i, len);
  }
  // One by one extract an element from heap
  for (let i = len - 1; i > 0; i--) {
    // Move current root to end
    // eslint-disable-next-line no-param-reassign
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // call max heapify on the reduced heap
    heapify(arr, 0, i);
  }
  return arr;
};

Merge sort

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The major portion of the algorithm is given two sorted arrays, and we have to merge them into a single sorted array. The whole process of sorting an array of N integers can be summarized into three steps

  • Divide the array into two halves.
  • Sort the left half and the right half using the same recurring algorithm.
  • Merge the sorted halves.
typescript
1
2
3
4
5
6
7
8
9
10
11
12
function merge(a, b) {
  const result = [];
  while (a.length > 0 && b.length > 0) result.push(a[0] < b[0] ? a.shift() : b.shift());
  return result.concat(a.length ? a : b);
}
export const MergeSort = (arr: number[]): 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));
};

Counting sort

The counting sort algorithm works by first creating a list of the counts or occurrences of each unique value in the list. It then creates a final sorted list based on the list of counts.

One important thing to remember is that counting sort can only be used when you know the range of possible values in the input beforehand.

typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
export const CountingSort = (
  originalArray: number[],
  smallestElement?: number,
  biggestElement?: number,
) => {
  if (originalArray.length <= 1) return originalArray;
  // Init biggest and smallest elements in array in order to build number bucket array later.
  let detectedSmallestElement = smallestElement || originalArray[0];
  let detectedBiggestElement = biggestElement || originalArray[0];

  if (smallestElement === undefined || biggestElement === undefined) {
    originalArray.forEach((element) => {
      // Visit element.

      // Detect biggest element.
      if (element > detectedBiggestElement) {
        detectedBiggestElement = element;
      }

      // Detect smallest element.
      if (element < detectedSmallestElement) {
        detectedSmallestElement = element;
      }
    });
  }

  // Init buckets array.
  const buckets = new Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0);
  // origin array is [1, 3, -1, -3, 5, 3, 6, 7], biggestElement is 7, smallestElement is -3
  // buckets is [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

  originalArray.forEach((element) => {
    buckets[element - detectedSmallestElement] += 1;
  });
  // buckets is [1, 0, 1, 0, 1, 0, 2, 0, 1, 1, 1]

  let sortedIndex = 0;
  for (let j = 0; j < buckets.length; j++) {
    while (buckets[j] > 0) {
      // eslint-disable-next-line no-param-reassign
      originalArray[sortedIndex++] = j + detectedSmallestElement;
      buckets[j]--;
    }
  }

  return originalArray;
};

Bucket sort

Bucket sort is a comparison sort algorithm that operates on elements by dividing them into different buckets and then sorting these buckets individually. Each bucket is sorted individually using a separate sorting algorithm like insertion sort, or by applying the bucket sort algorithm recursively.

Bucket sort is mainly useful when the input is uniformly distributed over a range. For example, imagine you have a large array of floating point integers distributed uniformly between an upper and lower bound.

You could use another sorting algorithm like merge sort, heap sort, or quick sort. However, those algorithms guarantee a best case time complexity of O(nlogn).

Using bucket sort, sorting the same array can be completed in O(n) time.

typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import { CountingSort } from './CountingSort';

export const BucketSort = (nums: number[], bucketSize: number = 5) => {
  const arr = nums;
  if (arr.length <= 1) {
    return arr;
  }

  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]; // 输入数据的最大值
    }
  }

  // 桶的初始化
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);

  // 利用映射函数将数据分配到各个桶中
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
    if (buckets[bucketIndex] === undefined) {
      buckets[bucketIndex] = [];
    }
    buckets[bucketIndex].push(arr[i]);
  }

  arr.length = 0;
  for (let i = 0; i < buckets.length; i++) {
    const sorted = CountingSort(buckets[i]);
    arr.push(...sorted);
  }

  return arr;
};