Неграфовые алгоритмы сортировки

28 февраля 2024 г.

Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом

Это краткий дополненный конспект части об алгоритмах сортировки в книге Гид по Computer Science, Вильям Спрингер.

Зачем создавать свой алгоритм сортировки когда уже есть готовый?

• готовый алгоритм сортировки неустойчивый, а вам необходим устойчивый
• у вас есть дополнительная информация о сортируемых данных, благодаря которой значительно сократить время выполнения алгоритма.

Наиболее эффективно изменить алгоритм сортировки можно, если:

• данные уже почти отсортированы;
• данные расположены в обратном или почти в обратном порядке;
• данные представляют собой конечное число дискретных значений, относительно малое по сравнению с количеством сортируемых элементов.

Большинство алгоритмов сортировки — сортировка сравнением. Два элемента сортируемого списка сравниваются с помощью некоторой операции. Она определяет, что один из элементов меньше или равен другому (размещается перед ним).

Сложность таких алгоритмов обычно определяется количеством требуемых операций сравнения.

Вспомогательные функции, которые используются в примерах алгоритмов ниже.

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};

Сортировки для малых наборов данных

Сортировка пузырьком (bubble sort)

Такая сортировка не имеет практической пользы, но хорошо показывает, как работает сортировка. Она эффективна, если список уже почти отсортирован. Если элементы не нужно менять местами - не производится никаких действий.

Алгоритм

1. 1) Сравнивается каждая пара соседних элементов
2. 2) Если элементы не расположены в правильном порядке их меняют местами

В худшем случае время выполнения O(n^2), в лучшем (список отсортирован или почти отсортирован) 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)

Выполняется путем перебора элементов массива.

Алгоритм

• Каждый элемент добавляется в конец массива.
• Если он больше чем последний элемент, остается на своем месте. Если меньше, то вставляем его в нужное место, сместив элементы после него на одну ячейку в конец.

1
2/*Сортировка вставками
3Полагается, что начало массива уже отсортировано (изначально 1 элемент). Алгоритм берет первый неотсортированный элемент (индекс 1) и последовательно сравнивает его с отсортированными, находя нужное место. После этого длина отсортированной части увеличивается (теперь уже два отсортированных элемента) и алгоритм переходит к следующему элементу (индекс 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}

Наилучшая сложность такой сортировки - O(n), когда массив уже отсортирован.

Наихудшая - O(n^2), когда массив отсортирован в обратном порядке.

На практике может применяться на небольших участках массива в рекурсивных алгоритмах (быстрая сортировка, сортировка слиянием).

Сортировка больших наборов данных

Пирамидальная сортировка

Делит входные данные на отсортированную и неотсортированную части и поэтапно перемещает элементы в отсортированную часть.

Требует предварительной обработки данных.

Сложность:

1. 1) из данных строится макс куча - требует O(n) операций (O(n lg n) в некоторых случаях).
2. 2) самый большой элемент кучи многократно извлекается и вставляется в массив или в конец кучи - O(lg n).

Наилучшая и наихудшая производительность алгоритма -O(n lg n), но на практике наилучшее время выполнения быстрее примерно в два раза.

Больше о построении кучи можете узнать здесь.

Алгоритм:

1) Из данных строим кучу.

2) Меняем первый и последний элементы элемент кучи.

3) Опускаем первый элемент кучи на положенное ему место до указанного последнего элемента кучи.

4) Уменьшаем индекс последнего элемента на один и повторяем 2 и 3 пункты.

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)

Список сортируется рекурсивно.

1. 1) массив данных делится на несколько массивов поменьше,
2. 2) эти массивы сортируются, а затем объединяются.

При чистом слияние можно продолжать деление, пока в каждом меньшем массиве не останется 1 элемент. На практике обычно прекращают деление, когда наборы достаточно малы, чтобы использовать алгоритм с наилучшим временем выполнения для небольших наборов данных (например, сортировку вставками).

Два отсортированных массива размером k, можно объединить в один полностью упорядоченный с числом сравнений k или 2k – 1.

Общее время выполнения O(n lg n) - O(lg n) комбинированных шагов, каждый из которых занимает O(n) времени.

1function mergeSort(arr) {
2	if (arr.length <= 1) return arr;
3
4	// середина массива
5	let middle = Math.floor(arr.length / 2);
6
7	// два подмассива, которые будут сортироваться отдельно
8	let left = arr.slice(0, middle);
9	let right = arr.slice(middle);
10
11	// слияние отсортированных подмассивов
12	return mergeSortedArrays(mergeSort(left), mergeSort(right));
13}
14
15function mergeSortedArrays(arr1, arr2) {
16	// Результат слияния
17	let newArray = [];
18
19	// текущие индексы сравниваемых элементов
20	let index1 = 0;
21	let index2 = 0;
22
23	// сравнение активных элементов
24	while (index1 < arr1.length && index2 < arr2.length) {
25		let min = null;
26		if (comparator(arr1[index1], arr2[index2]) <= 0) {
27			min = arr1[index1]; // добавление минимального элемента в массив
28			index1++; // сдвиг индекса активного элемента первого массива
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)

Наихудшее время выполнения O(n^2), но на практике он обычно работает за среднее время O(n lg n).

Алгоритм:

1. 1) Выбираем опорный элемент.
2. 2) Упорядочиваем остальные элементы относительно опорного. Слева - меньше либо равны ему, справа - больше или равны.
3. 3) 1 и 2 пункт рекурсивно повторяются для правого и левого под сегмента, до тех пор пока каждый сегмент не будет содержать одно или ноль значений.

Количество требуемых операций зависит от:

1. 1) выбранного опорного элемента,
2. 2) значений, которые необходимо отсортировать.

Выбор опорного элемента:

Метод Ломуто - выбираем последний элемент в качестве опорного. Невыгоден для уже отсортированного массива, так как время выполнения в этом случае будет O(n^2). На каждой итерации сегмент будет уменьшаться только на один элемент.

Наилучший вариант, в качестве опорного выбрать средний элемент (случайный или медиану из трех случайных).

Идеальный вариант: опорный элемент - точная медиана сортируемых данных, а каждый из подразделов содержит половину оставшихся.

При неслучайном выборе данных можно подвергнуть алгоритм атаке злоумышленника - он может размещать данные так, чтобы опорный элемент всегда находился с одной и той же стороны от элемента, с которым он сравнивается, увеличивая время выполнения до O(n^2).

Также будет плохо работать с данными, которые содержать большое количество повторяющихся значений (задача о голландском национальном флаге). Решение - используем сортировку не на два, а на три раздела (меньше, равно, больше). Так средний раздел не будет нуждаться в дальнейшей сортировке.

Преимущества по сравнению с сортировкой слиянием:

1. 1) включают в себя сортировку на месте (в исходной памяти, без использования дополнительной памяти),
2. 2) более простой внутренний цикл.

Недостатки:

1. 1) Наихудшее время выполнения O(n^2),
2. 2) Нет стабильности - во время разбиения могут переставляться элементы с одинаковым ключом
3. 3) Сортировка на месте не работает если данные представлены в виде связного списка.

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	// индекс опорного элемента
8	let pivot = partition(arr, start, end);
9
10	// рекурсивная сортировка подмассивов
11	quickSort(arr, start, pivot - 1);
12	quickSort(arr, pivot + 1, end);
13
14	return arr;
15}
16
17function partition(arr, start, end) {
18	// Берем в качестве опорного последний элемент подмассива
19	let pivotValue = arr[end];
20
21	// изначально считаем, что pivotValue минимальное значение
22	// и должно находиться в начале массива
23	let pivotIndex = start;
24
25	// перебираем все элементы
26	for (let i = start; i < end; i++) {
27		// значения меньше опорного перемещаем перед ним
28		if (comparator(arr[i], pivotValue) < 0) {
29			swap(arr, i, pivotIndex);
30			pivotIndex++;
31		}
32	}
33
34	// ставим опорный элемент в нужное место
35	swap(arr, pivotIndex, end);
36
37	return pivotIndex;
38}

Сортировки без сравнения

Используют для сортировки ключи (дополнительную информацию) сортируемых данных.

Сортировка подсчетом

Это стабильный метод сортировки.

Для данных размером n, где каждый элемент имеет ключ - положительное число со значением не более k:

Алгоритм:

1. 1) Создаем массив длиной k.
2. 2) Перебираем в цикле все элементы, а в этот массив записываем количество вхождений каждого ключа (строим частотную гистограмму для значений ключа).
3. 3) Еще раз проходимся по массиву и заменяем каждое значение на количество ключей с меньшими значениями - теперь каждая ячейка содержит правильную позицию для первого элемента с этим ключом.
4. 4) Перемещаем каждый элемент исходных данных в позицию равную значению в соответствующей ячейке массива ключей + 1 (для того, чтобы, если есть элемент с таким же ключом, разместить его в следующей ячейке выходного массива).
   

Пример: Дан массив, в котором цифра - ключ, буква значение. [1a, 5b, 3a, 1c, 3c, 2b, 3a, 3c, 5b, 2b, 1c]. Проходя по массиву получаем гистограмму [3, 2, 4, 2 ] - 3 единицы, 2 двойки, 4 тройки, 2 пятерки. Гистограмма говорит нам о том, что первый элемент с каждым ключом должен появляться в следующих позициях: [0, 3, 5, 9].

Снова проходим по исходному массиву. Первый элемент равен 1 и перейдет в ячейку 0. Второй элемент с ключом 3 пойдет в третью ячейку и так далее. Помещая элемент в выходной массив, увеличиваем соответствующее значение в массиве ключей на единицу. Например, после размещения первых шести элементов массив ключей принял вид [2, 4, 7, 10], и мы знаем, что следующий элемент, 3a, попадет в ячейку 7 выходного массива.

В примерах реализации сортировки подсчетом на JavaScript ниже, максимальное значение ключа известно и передается в функцию как 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"];

Также существует вариант с уменьшением индекса в массиве ключей:

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};

Для данных, состоящих только из целочисленных значений, подойдет следующий вариант алгоритма:

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	// Здесь происходит следующее
11	// i = 0, countArr[1] + 1
12	// i = 1, countArr[5] + 1
13	// i = 2, countArr[3] + 1
14	// i = 3, countArr[1] + 1 и так далее
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];

На иллюстрации ниже вы можете проследить за тем, что именно происходит в последнем цикле алгоритма.

Весь процесс требует:

1. 1) инициализация массива ключей размером к и выходного массива размером n.
2. 2) два цикла для входного массива - заполнение массива ключей и перемещение элементов в выходной массив.
3. 3) один цикл для массива значений - просуммировать значения и определить конечные позиции ключей.

Среднее время выполнения O(n + k). Если k мало по сравнению с n - O(n).

Поразрядная сортировка

Поразрядная сортировка - это старый метод сортировки. Его использовал Герман Холлерит для счетно-аналитических машин в 1887 году.

Хороший пример, телефонный справочник/телефонная книга - данные сортируются побуквено.

Сложность O(wn) для ключей с длиной слова w. Каждый элемент помещается в ячейку (за постоянное время) один раз для каждого символа ключа. Если w постоянна, то сложность O(n).

Получить разряд числа в десятичной системе счисления:

Каждое число можно представить как сумму произведений из разрядов и числа 10 в нужной степени;

Например, число 269 = 2×10² + 6×10¹ + 9×10⁰

Для того, чтобы найти разряд, необходимо

1. 1) Поделить число на 10 в степени порядкового номера разряда, начиная справа налево. 0 - самый младший разряд.
2. 2) Найти остаток от деления получившегося значения на 10.

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

Например, для числа 269

единицы 269/10⁰ = 269; 269 % 10 = 9

десятки 269/10¹ = 26; 26 % 10 = 6

сотни 269/10² = 2; 2 % 10 = 2

Существует несколько вариантов поразрядной сортировки:

• сортировку по младшему разряду (least significant digit, LSD)
• сортировку по старшему разряду (most significant digit, MSD).

Рассмотрим сортировку по младшему разряду (LSD).

Чтобы сортировка была стабильной, сгруппируем ключи по младшему разряду, но сохраним их относительный порядок.

Алгоритм:

1. 1) Получаем максимальное количество разрядов числа в массиве. Для этого находим максимальное число.
2. 2) На основании используемого в ключах алфавита, создадим по ячейке для каждой буквы этого алфавита. Например, если ключ десятичное число, то мы получим десять ячеек, помеченных цифрами от 0 до 9.
3. 3) Создадим цикл с количеством итераций равному макс. количеству разрядов.
4. 4) Внутри цикла проходимся по исходному массиву. Для каждого числа массива получаем значение по разряду. Разряд 0 - единицы, 1 - десятки, 2 сотни и т.д. Записываем элемент из массива в промежуточный массив по индексу равному значению полученного значение. Например, элемент с ключом 378 на первой итерации попадает в ячейку номер 8. На второй в ячейку 7, на третьей в ячейку 3. У этого числа три разряда, поэтому и три итерации.
5. 5) Оставаясь внутри цикла по разрядам для всех ненулевых значений промежуточного массива собираем значения в исходный массив.

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// ]

Как это работает?

Например, есть два ключа. Если их старшие разряды различаются, то ключ, который должен стоять первым при сортировке попадает в предшествующую ячейку. Если же старшие разряды одинаковы, они попадут в одну ячейку в том же порядке, в котором были отсортированы для предыдущего разряда.