Some Common Sorting Algorithms
Selection sort 、Bubble sort 、Insertion sort 、Merge sort 、Quick sort 、Heap sort 、Counting sort 、Radix sort 、Bucket sort
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.
1export const SelectionSort = (nums: number[]) => {
2 for (let i = 0; i < nums.length - 1; i++) {
3 let minIndex = i;
4 for (let j = i + 1; j < nums.length; j++) {
5 if (nums[j] < nums[minIndex]) {
6 minIndex = j;
7 }
8 }
9 if (minIndex !== i) {
10 // eslint-disable-next-line no-param-reassign
11 [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
12 }
13 }
14 return nums;
15};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.
1export const BubbleSort = (array: number[]) => {
2 let sorted = false;
3 while (!sorted) {
4 sorted = true;
5 for (let i = 0; i < array.length - 1; i++) {
6 if (array[i] > array[i + 1]) {
7 sorted = false;
8 // eslint-disable-next-line no-param-reassign
9 [array[i], array[i + 1]] = [array[i + 1], array[i]];
10 }
11 }
12 }
13 return array;
14};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.
1export const InsertionSort = (arr: number[]) => {
2 for (let i = 1; i < arr.length; i++) {
3 for (let j = i; j > 0; j--) {
4 if (arr[j] < arr[j - 1]) {
5 // eslint-disable-next-line no-param-reassign
6 [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
7 }
8 }
9 }
10 return arr;
11};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)
1// Divide and Conquer
2export const QuickSort = (array: number[]) => {
3 if (array.length <= 1) return array;
4 const pivot = array[array.length - 1];
5 const left = [];
6 const right = [];
7 for (let i = 0; i < array.length - 1; i++) {
8 if (array[i] < pivot) {
9 left.push(array[i]);
10 } else {
11 right.push(array[i]);
12 }
13 }
14 return [...QuickSort(left), pivot, ...QuickSort(right)];
15};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.
1/**
2 * @description 堆排序
3 * @param arr - 待排序数组
4 * @param i - index of the element to be heapified
5 * @param len - size of the heap
6 * @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.
7 */
8export const heapify = (arr: number[], i: number, len: number) => {
9 let largest = i;
10 // left child
11 const left = 2 * i + 1;
12 // right child
13 const right = 2 * i + 2;
14 // compare left child with root, if left child is larger than root, then largest is left child
15 if (left < len && arr[left] > arr[largest]) {
16 largest = left;
17 }
18 // compare right child with root, if right child is larger than root, then largest is right child
19 if (right < len && arr[right] > arr[largest]) {
20 largest = right;
21 }
22 // if largest is not root, swap and continue heapifying
23 if (largest !== i) {
24 // eslint-disable-next-line no-param-reassign
25 [arr[i], arr[largest]] = [arr[largest], arr[i]];
26 heapify(arr, largest, len);
27 }
28};
29
30export const HeapSort = (arr: number[]) => {
31 const len = arr.length;
32 // build heap
33 // `floor(len / 2)` doesn't mean the middle of the tree, but the number of nodes that aren't leaves.
34 for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
35 heapify(arr, i, len);
36 }
37 // One by one extract an element from heap
38 for (let i = len - 1; i > 0; i--) {
39 // Move current root to end
40 // eslint-disable-next-line no-param-reassign
41 [arr[0], arr[i]] = [arr[i], arr[0]];
42 // call max heapify on the reduced heap
43 heapify(arr, 0, i);
44 }
45 return arr;
46};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.
1function merge(a, b) {
2 const result = [];
3 while (a.length > 0 && b.length > 0) result.push(a[0] < b[0] ? a.shift() : b.shift());
4 return result.concat(a.length ? a : b);
5}
6export const MergeSort = (arr: number[]): number[] => {
7 if (arr.length <= 1) return arr;
8 const mid = Math.floor(arr.length / 2);
9 const left = arr.slice(0, mid);
10 const right = arr.slice(mid);
11 return merge(MergeSort(left), MergeSort(right));
12};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.
1export const CountingSort = (
2 originalArray: number[],
3 smallestElement?: number,
4 biggestElement?: number,
5) => {
6 if (originalArray.length <= 1) return originalArray;
7 // Init biggest and smallest elements in array in order to build number bucket array later.
8 let detectedSmallestElement = smallestElement || originalArray[0];
9 let detectedBiggestElement = biggestElement || originalArray[0];
10
11 if (smallestElement === undefined || biggestElement === undefined) {
12 originalArray.forEach((element) => {
13 // Visit element.
14
15 // Detect biggest element.
16 if (element > detectedBiggestElement) {
17 detectedBiggestElement = element;
18 }
19
20 // Detect smallest element.
21 if (element < detectedSmallestElement) {
22 detectedSmallestElement = element;
23 }
24 });
25 }
26
27 // Init buckets array.
28 const buckets = new Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0);
29 // origin array is [1, 3, -1, -3, 5, 3, 6, 7], biggestElement is 7, smallestElement is -3
30 // buckets is [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
31
32 originalArray.forEach((element) => {
33 buckets[element - detectedSmallestElement] += 1;
34 });
35 // buckets is [1, 0, 1, 0, 1, 0, 2, 0, 1, 1, 1]
36
37 let sortedIndex = 0;
38 for (let j = 0; j < buckets.length; j++) {
39 while (buckets[j] > 0) {
40 // eslint-disable-next-line no-param-reassign
41 originalArray[sortedIndex++] = j + detectedSmallestElement;
42 buckets[j]--;
43 }
44 }
45
46 return originalArray;
47};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.
1import { CountingSort } from './CountingSort';
2
3export const BucketSort = (nums: number[], bucketSize: number = 5) => {
4 const arr = nums;
5 if (arr.length <= 1) {
6 return arr;
7 }
8
9 let minValue = arr[0];
10 let maxValue = arr[0];
11 for (let i = 1; i < arr.length; i++) {
12 if (arr[i] < minValue) {
13 minValue = arr[i]; // 输入数据的最小值
14 } else if (arr[i] > maxValue) {
15 maxValue = arr[i]; // 输入数据的最大值
16 }
17 }
18
19 // 桶的初始化
20 const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
21 const buckets = new Array(bucketCount);
22
23 // 利用映射函数将数据分配到各个桶中
24 for (let i = 0; i < arr.length; i++) {
25 const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
26 if (buckets[bucketIndex] === undefined) {
27 buckets[bucketIndex] = [];
28 }
29 buckets[bucketIndex].push(arr[i]);
30 }
31
32 arr.length = 0;
33 for (let i = 0; i < buckets.length; i++) {
34 const sorted = CountingSort(buckets[i]);
35 arr.push(...sorted);
36 }
37
38 return arr;
39};