Non-Graph Sorting Algorithms

28 февраля 2024 г.

Dynamic visualization of 7 open-source sorting algorithms.

This is a brief, expanded set of notes covering the section on sorting algorithms from the book A Guide to Computer Science by William Springer.

Why create your own sorting algorithm when one already exists?

• you need a stable sort, while the default one is unstable;
• you have additional knowledge about the data that can significantly reduce runtime.

The most effective modifications are possible when:

• the data is already almost sorted;
• the data is in reverse or nearly reverse order;
• the data consists of a limited number of discrete values that is small compared to the number of elements.

Most sorting algorithms are comparison-based. Two elements are compared using some operation that determines which element should come first.

The complexity of such algorithms is usually determined by the number of comparisons required.

Below are helper functions used in the examples.

1const comparator = (a, b) => a - b;
2
3const swap = (arr, i, j) => {
4	let temp = arr[i];
5	arr[i] = arr[j];
6	arr[j] = temp;
7};

Sorting for small datasets

Bubble Sort

This sorting algorithm has no practical value, but it clearly demonstrates how sorting works. It is efficient when the list is already nearly sorted; if no swaps are needed, no work is performed.

Algorithm:

1. Compare each pair of adjacent elements
2. If they are in the wrong order, swap them

Example:

In the worst case, time complexity is O(n²), and in the best case (already or nearly sorted list) O(n).

1function bubbleSort(arr) {
2	for (let j = arr.length - 1; j > 0; j--) {
3		for (let i = 0; i < j; i++) {
4			if (comparator(arr[i], arr[i + 1]) > 0) {
5				swap(arr, i, i + 1);
6			}
7		}
8	}
9	return arr;
10}

Insertion sort

This algorithm works by iterating through the array.

Algorithm:

• Each element is added to the end of the array.
• If it is greater than the last element, it remains in its current position. If it is smaller, it is inserted into the correct position, and all subsequent elements are shifted one position to the right.

1
2/* Insertion Sort
3Assumes that the beginning of the array is already sorted (initially, it contains just one element). The algorithm takes the first unsorted element (at index 1) and compares it with the sorted elements to find its correct position. Once inserted, the sorted portion of the array grows (it now contains two sorted elements), and the algorithm moves on to the next unsorted element (at index 2). */
4
5function insertionSort(arr) {
6	for (let i = 1; i < arr.length; i++) {
7		let current = i;
8
9		while (
10			arr[current - 1] !== undefined &&
11			comparator(arr[current], arr[current - 1]) < 0
12		) {
13			swap(arr, current - 1, current);
14			current--;
15		}
16	}
17}

Best case complexity is O(n) (already sorted array).

Worst case is O(n²) (reverse sorted array).

In practice, it is often used on small subarrays in recursive algorithms (quicksort, mergesort).

Sorting large datasets

Heap Sort (Binary Heap Sort)

This algorithm divides data into a sorted and unsorted part and repeatedly moves elements into the sorted section.

It requires preprocessing of the data.

Complexity:

1. A max heap is built from the input data, which requires O(n) operations (or O(n log n) in some implementations).
2. The largest element is repeatedly extracted from the heap and placed into the array (or moved to the end of the heap), with each extraction taking O(log n).

The algorithm has a best-case and worst-case time complexity of O(n log n). In practice, however, the best-case execution time is often about twice as fast as the worst case.

You can learn more about heap construction here.

Algorithm:

1. Build a max heap from the input data.
2. Swap the first element (the root of the heap) with the last element in the heap.
3. Restore the heap property by moving the new root down to its correct position, considering only the heap up to the current last element.
4. Decrease the index of the last heap element by one and repeat steps 2 and 3 until the heap is empty.

1const simpleArr = [1, 5, 8, 10, 18, 2, 4, 9, 28, 305, 40, 7];
2const comparator = (a, b) => b - a;
3
4const swap = (arr, i, j) => {
5	let temp = arr[i];
6	arr[i] = arr[j];
7	arr[j] = temp;
8};
9
10class Heap {
11	constructor(comparator) {
12		this.arr = [];
13		this.comparator = comparator;
14	}
15
16	isCorrectOrder(first, second) {
17		return this.comparator(first, second) < 0;
18	}
19
20	getLeftChildIndex(parentIndex) {
21		return 2 * parentIndex + 1;
22	}
23
24	getRightChildIndex(parentIndex) {
25		return 2 * parentIndex + 2;
26	}
27
28	getParentIndex(childIndex) {
29		return Math.floor((childIndex - 1) / 2);
30	}
31
32	leftChild(parentIndex) {
33		return this.arr[this.getLeftChildIndex(parentIndex)];
34	}
35
36	rightChild(parentIndex) {
37		return this.arr[this.getRightChildIndex(parentIndex)];
38	}
39
40	parent(childIndex) {
41		return this.arr[this.getParentIndex(childIndex)];
42	}
43
44	hasParent(childIndex) {
45		return this.getParentIndex(childIndex) >= 0;
46	}
47
48	hasLeftChild(parentIndex) {
49		return this.getLeftChildIndex(parentIndex) < this.arr.length;
50	}
51
52	hasRightChild(parentIndex) {
53		return this.getRightChildIndex(parentIndex) < this.arr.length;
54	}
55
56	buildHeap(array) {
57		this.arr = array;
58		let i = array.length - 1;
59		while (i > 1) {
60			this.heapifyUp(i);
61			i--;
62		}
63	}
64	heapifyUp(startIndex) {
65		let currentIndex = startIndex ?? this.arr.length - 1;
66
67		while (
68			this.hasParent(currentIndex) &&
69			!this.isCorrectOrder(
70				this.parent(currentIndex),
71				this.arr[currentIndex]
72			)
73		) {
74			let parentIndex = this.getParentIndex(currentIndex);
75			this.swap(currentIndex, parentIndex);
76			currentIndex = parentIndex;
77		}
78	}
79
80	swap(indexOne, indexTwo) {
81		const tmp = this.arr[indexTwo];
82		this.arr[indexTwo] = this.arr[indexOne];
83		this.arr[indexOne] = tmp;
84	}
85
86	heapifyDown(customStartIndex = 0, last) {
87		let currentIndex = customStartIndex;
88		let nextIndex = null;
89		let lastIndex = last || this.arr.length - 1;
90
91		while (this.hasLeftChild(currentIndex)) {
92			if (
93				this.hasRightChild(currentIndex) &&
94				this.isCorrectOrder(
95					this.rightChild(currentIndex),
96					this.leftChild(currentIndex)
97				)
98			) {
99				nextIndex = this.getRightChildIndex(currentIndex);
100			} else {
101				nextIndex = this.getLeftChildIndex(currentIndex);
102			}
103
104			if (
105				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
106			) {
107				break;
108			}
109
110			if (nextIndex < lastIndex) {
111				this.swap(currentIndex, nextIndex);
112				currentIndex = nextIndex;
113			} else {
114				break;
115			}
116		}
117	}
118}
119
120const heapSort = (array) => {
121	const heap = new Heap(comparator);
122	heap.buildHeap(array);
123
124	for (var i = array.length - 1; i > 0; i--) {
125		heap.swap(i, 0);
126		heap.heapifyDown(0, i);
127	}
128
129	return heap.arr;
130};
131
132console.log(heapSort(simpleArr));
133// [
134// 	1,   2,  4,  5,  7,
135// 	8,   9, 10, 18, 28,
136//    40, 305
137//  ]
138

Merge sort

A recursive sorting algorithm:

1. split the array into smaller subarrays
2. sort them
3. merge them back together

Example:

In a pure merge sort implementation, the array can continue to be divided until each subarray contains only one element. In practice, however, the division usually stops once the subarrays become small enough to be sorted more efficiently using an algorithm that performs well on small datasets, such as insertion sort.

Two sorted arrays of size k can be merged into one fully sorted array using at least k and at most 2k − 1 comparisons.

The total running time of merge sort is O(n log n), because there are O(log n) merge levels, each requiring O(n) work.

1function mergeSort(arr) {
2	if (arr.length <= 1) return arr;
3
4	// middle of the array
5	let middle = Math.floor(arr.length / 2);
6
7	// two subarrays that will be sorted independently
8	let left = arr.slice(0, middle);
9	let right = arr.slice(middle);
10
11	// merge of sorted subarrays
12	return mergeSortedArrays(mergeSort(left), mergeSort(right));
13}
14
15function mergeSortedArrays(arr1, arr2) {
16	// Result of the merge
17	let newArray = [];
18
19	//current indices of the compared elements
20	let index1 = 0;
21	let index2 = 0;
22
23	// comparing the active elements
24	while (index1 < arr1.length && index2 < arr2.length) {
25		let min = null;
26		if (comparator(arr1[index1], arr2[index2]) <= 0) {
27			min = arr1[index1]; //adding the smallest element to the array
28			index1++; // advancing the index of the active element in the first array
29		} else {
30			min = arr2[index2];
31			index2++;
32		}
33
34		newArray.push(min);
35	}
36
37	return [...newArray, ...arr1.slice(index1), ...arr2.slice(index2)];
38}

Quick sort

The worst-case running time is O(n²), but in practice, the algorithm typically runs in O(n log n) on average.

Algorithm steps:

1. Select a pivot element.
2. Partition the remaining elements around the pivot: elements smaller than or equal to the pivot are placed on the left, and elements greater than or equal to the pivot are placed on the right.
3. Recursively apply steps 1 and 2 to the left and right subarrays until each subarray contains at most one element.

The number of operations required depends on:

1. The choice of the pivot element.
2. The values being sorted.

Choosing the Pivot Element:

Lomuto method — the last element is selected as the pivot. This approach performs poorly on already sorted arrays because the time complexity degrades to O(n²). During each iteration, the segment is reduced by only one element.

The optimal strategy is to select the middle element as the pivot—for example, a randomly chosen element or the median of three.

The ideal scenario is when the pivot is the exact median of the input data, causing the array to be split into two equally sized partitions at each step. This produces the optimal O(n log n) running time.

Deterministic pivot selection can make the algorithm vulnerable to adversarial input. By carefully arranging the data, an attacker can force the pivot to consistently produce highly unbalanced partitions, degrading the algorithm's performance to O(n²).

Quicksort also performs poorly on datasets that contain a large number of duplicate values (the Dutch National Flag problem). A common solution is to partition the array into three sections instead of two: elements less than, equal to, and greater than the pivot. This way, the middle section, which contains all elements equal to the pivot, does not require any further sorting.

Advantages over merge sort:

1. It is an in-place sorting algorithm, meaning it sorts the data in the original array without requiring additional memory.
2. It has a simpler inner loop.

Disadvantages:

1. The worst-case time complexity is O(n²).
2. It is not stable—during partitioning, elements with equal keys may be reordered.
3. In-place partitioning is not suitable when the data is stored as a linked list.

1function quickSort(arr, start, end) {
2	if (start === undefined) start = 0;
3	if (end === undefined) end = arr.length - 1;
4
5	if (start >= end) return;
6
7	// pivot index
8	let pivot = partition(arr, start, end);
9
10	// Recursive subarray sorting
11	quickSort(arr, start, pivot - 1);
12	quickSort(arr, pivot + 1, end);
13
14	return arr;
15}
16
17function partition(arr, start, end) {
18	// Choose the last element of the subarray as the pivot.
19	let pivotValue = arr[end];
20
21    // Initially, assume that pivotValue is the smallest value
22    // and should be placed at the beginning of the array.
23	let pivotIndex = start;
24
25	//Iterate through all elements.
26	for (let i = start; i < end; i++) {
27		// Move elements smaller than the pivot before it.
28		if (comparator(arr[i], pivotValue) < 0) {
29			swap(arr, i, pivotIndex);
30			pivotIndex++;
31		}
32	}
33
34	//  Place the pivot in its correct position.
35	swap(arr, pivotIndex, end);
36
37	return pivotIndex;
38}

Non-comparison sorting algorithms

It sorts the keys (additional information) associated with the data being sorted.

Counting Sort

This is a stable sorting algorithm.

Given a dataset of size n, where each element has a key represented by a positive integer with a value no greater than k:

1. Algorithm:
2. Create an array of size k.
3. Iterate through all the elements and store the number of occurrences of each key in the array (i.e., build a frequency histogram of the key values).
4. Iterate through the count array again and replace each value with the number of keys that are smaller than the corresponding key. After this step, each entry contains the correct starting position for the first element with that key.
5. Move each element from the input array to the position indicated by its corresponding value in the count array, then increment that value by 1. This ensures that if another element has the same key, it is placed in the next available position in the output array.

Example: Given the following array, where the number is the key and the letter is the value:

[1a, 5b, 3a, 1c, 3c, 2b, 3a, 3c, 5b, 2b, 1c]

Iterating through the array, we obtain the histogram [3, 2, 4, 2] — 3 ones, 2 twos, 4 threes, and 2 fives. The histogram tells us that the first element with each key should appear at the following positions: [0, 3, 5, 9].

We then iterate through the original array again. The first element has the key 1, so it is placed into position 0. The first element with the key 3 is placed into position 5, and so on. After placing an element into the output array, we increment the corresponding value in the key array by 1. For example, after placing the first six elements, the key array becomes [2, 4, 7, 10], and we know that the next element, 3a, will be placed into position 7 of the output array.

In the JavaScript implementations of counting sort below, the maximum key value is known in advance and is passed to the function as k.

1const someArray = [`1a`, `5b`, `3a`, `1c`, `3c`, `2b`, `3a`, `3c`, `5b`, `2b`, `1c`, `8c`];
2
3const countingSort = (arr, k) => {
4	const countArr = new Array(k + 1).fill().map(() => 0);
5	let output = new Array(arr.length);
6
7	for (let i = 0; i < arr.length; i++) {
8		countArr[+arr[i][0]] += 1;
9	}
10
11	for (let i = 1; i <= k; i++) {
12		countArr[i] = countArr[i] + countArr[i - 1];
13	}
14
15	for (let i = 0; i < arr.length; i++) {
16		let j = arr[i][0] - 1;
17
18		output[countArr[j]] = arr[i];
19		countArr[j] = countArr[j] + 1;
20	}
21
22	return output;
23};
24
25console.log(countingSort(someArray, 8));
26// ["1c", "1c", "1a", "2b", "2b", "3c", "3a", "3c", "3a", "5b", "5b", "8c"];

An alternative implementation decrements the corresponding index in the count array:

1const countingSort = (arr, k) => {
2	const countArr = new Array(k + 1).fill().map(() => 0);
3	let output = new Array(arr.length);
4
5	for (let i = 0; i < arr.length; i++) {
6		countArr[+arr[i][0]] += 1;
7	}
8
9	for (let i = 1; i <= k; i++) {
10		countArr[i] = countArr[i] + countArr[i - 1];
11	}
12
13	for (let i = 0; i < arr.length; i++) {
14		let j = arr[i][0];
15		countArr[j] = countArr[j] - 1;
16		output[countArr[j]] = arr[i];
17	}
18
19	return output;
20};

For datasets containing only integer values, the following algorithm is suitable:

1const simpleArray = [`1`, `5`, `3`, `1`, `3`, `2`, `3`, `3`, `5`, `2`, `1`];
2
3const simpleCountingSort = (arr, k) => {
4	const countArr = new Array(k + 1).fill().map(() => 0);
5
6	for (let i = 0; i < arr.length; i++) {
7		countArr[+arr[i][0]] += 1;
8	}
9
10	// Here's what happens:
11	// i = 0, countArr[1] + 1
12	// i = 1, countArr[5] + 1
13	// i = 2, countArr[3] + 1
14	// i = 3, countArr[1] + 1 etc.
15
16	let b = 0;
17	for (let i = 0; i < k + 1; i++) {
18		for (let j = 0; j < countArr[i]; j++) {
19			arr[b] = i;
20			b++;
21		}
22	}
23
24	return arr;
25};
26
27console.log(simpleCountingSort(simpleArray, 5));
28// [1, 1, 1, 2, 2, 3, 3, 3, 3, 5, 5];

The illustration below shows exactly what happens during the final loop of the algorithm.

The entire process requires:

1. Initializing a count array of size k and an output array of size n.
2. Two passes over the input array: one to populate the count array and another to move the elements into the output array.
3. One pass over the count array to accumulate the counts and determine the final positions of the keys.

The average running time is O(n + k). If k is small compared to n, the time complexity is O(n).

Radix Sort

Radix sort is an old sorting algorithm. It was used by Herman Hollerith in tabulating machines in 1887.

A good example is a telephone directory or phone book, where entries are sorted one letter at a time.

The time complexity is O(wn), where w is the number of digits (or characters) in each key. Each element is placed into a bucket (in constant time) once for each digit of the key. If w is constant, the time complexity becomes O(n).

Extracting a digit from a decimal number:

Any number can be represented as the sum of its digits multiplied by powers of 10.

For example:

269 = 2 × 10² + 6 × 10¹ + 9 × 10⁰

To extract a digit:

1. Divide the number by 10 raised to the power of the digit's position, counting from right to left. Position 0 corresponds to the least significant digit.
2. Find the remainder when the resulting value is divided by 10.

1Math.floor(value/Math.pow(k, i)) % k
2//  к = 10, 0 <= i < number length

For example, for the number 269:

Ones: 269 / 10⁰ = 269; 269 % 10 = 9

Tens: 269 / 10¹ = 26; 26 % 10 = 6

Hundreds: 269 / 10² = 2; 2 % 10 = 2

There are several variants of radix sort:

• Least Significant Digit (LSD) radix sort.
• Most Significant Digit (MSD) radix sort.

Let's consider Least Significant Digit (LSD) radix sort.

To keep the sort stable, we group the keys by their least significant digit while preserving their relative order.

Algorithm:

1. Determine the maximum number of digits among the numbers in the array. To do this, find the largest number.
2. Based on the alphabet used by the keys, create one bucket for each possible symbol. For example, if the keys are decimal numbers, create ten buckets labeled 0 through 9.
3. Create a loop that runs for the maximum number of digits.
4. Inside the loop, iterate through the input array. For each number, extract the digit at the current position. Position 0 corresponds to the ones place, 1 to the tens place, 2 to the hundreds place, and so on. Place the element into the corresponding bucket based on the extracted digit. For example, the element with the key 378 is placed into bucket 8 during the first iteration, bucket 7 during the second iteration, and bucket 3 during the third iteration. Since the number has three digits, it participates in three iterations.
5. Still inside the digit loop, collect the elements from all non-empty buckets back into the original array.

1const radixSort = (array, k) => {
2	const rank = Math.max(...array).toString().length;
3	let bins = new Array(k).fill().map(() => []);
4	for (let i = 0; i < rank; i++) {
5		array.forEach((value) => {
6			const digit = Math.floor(value/Math.pow(k, i)) % k
7			bins[digit].push(value);
8		});
9		let indexValue = 0;
10		bins.forEach((values) => {
11			for (let i = 0; values.length > 0; i++) {
12				array[indexValue] = values.shift(0);
13				indexValue++;
14			}
15		});
16	}
17	return array;
18};
19
20const array = [16, 890, 46, 38, 59, 24, 146, 7, 368, 2005, 12];
21
22console.log(radixSort(array, 10));
23// [
24//     7,  12,   16,  24,
25//    38,  46,   59, 146,
26//   368, 890, 2005
27// ]

How does it work?

Consider two keys. If their more significant digits differ, the key that should come first in the sorted order is placed into an earlier bucket. If their more significant digits are the same, they are placed into the same bucket in the same relative order established during the previous digit's sort.