Продолжаем наш непотопляемый цикл статей о сортировках. В обычной прикладной разработке они не нужны, но помогают лучше понять компьютеры и прокачать алгоритмическое мышление.
Сортировка — это процесс, когда какой-то набор чисел выстраивают по возрастанию или убыванию. Сортировать можно просто числа или целые таблицы с кучей значений. Когда вы сортируете что-то в Экселе или открываете список контактов в телефоне, работает какой-то алгоритм сортировки.
В обычных сортировках мы разными способами сравниваем элементы массива между собой. Но есть пара сортировок, в которых нет сравнений, но массив всё равно выстраивается по порядку. Рассказываем, как работает такая магия на примере сортировки подсчётом.
Сортировка подсчётом лучше всего работает при таких условиях:
- массив очень большой — значений много;
- эти значения лежат в известном нам диапазоне (например, это диапазон работы какого-то датчика);
- диапазон намного меньше, чем размер массива, то есть единицы данных могут повторяться.
Принцип работы
Главная идея алгоритма — посчитать, сколько раз встречается каждый элемент в массиве, а потом заполнить исходный массив результатами этого подсчёта. Для этого нам нужен вспомогательный массив, где мы будем хранить результаты подсчёта. Даже если нам надо отсортировать миллион чисел, мы всё равно знаем диапазон этих чисел заранее, например, от 1 до 100. Это значит, что во вспомогательном массиве будет не миллион элементов, а сто.
В общем виде всё работает так:
- Мы создаём вспомогательный массив и на старте заполняем его нулями.
- Проходим по всему исходному массиву и смотрим очередное значение в ячейке.
- Берём содержимое этой ячейки и увеличиваем на единицу значение вспомогательного массива под этим номером. Например, если мы встретили число 5, то увеличиваем на единицу пятый элемент вспомогательного массива. Если встретили 13 — тринадцатый.
- После цикла во вспомогательном массиве у нас хранятся данные, сколько раз встречается каждый элемент.
- Теперь мы проходим по вспомогательному массиву, и если в очередной ячейке лежит что-то больше нуля, то мы в исходный массив столько же раз отправляем номер этой ячейки. Например, в первой ячейке вспомогательного массива лежит число 7. Это значит, что в исходный массив мы отправляем единицу 7 раз подряд.
В итоге мы получаем отсортированный массив без сравнения элементов. Вот как это выглядит на практике:
Зачем нужна эта сортировка
Допустим, у нас есть какой-то прибор, который выдаёт результаты в определённом диапазоне, например показывает сейсмоактивность этом регионе в диапазоне от 0 до 100. Он работает круглосуточно и каждые 2 секунды пишет в лог новое значение текущей активности землетрясений. За год получается 15 миллионов записей. Сортировка подсчётом отлично подходит для такого массива, потому что мы знаем диапазон и этот диапазон гораздо меньше общего количества элементов массива.
Сортировка подсчётом на JavaScript
Скопируйте и запустите этот код в браузере, чтобы проверить сортировку подсчётом в деле. Мы добавили комментарий к каждой строке кода, чтобы можно было лучше разобраться в работе алгоритма на каждом этапе.
// сортировка подсчётом
let countingSort = (arr, min, max) => {
// начинаем с минимального значения диапазона
let i = min,
// вспомогательная переменная для цикла
j = 0,
// получаем длину массива
len = arr.length,
// вспомогательный массив, где будем хранить результаты подсчёта
count = [];
// сначала заполняем нулями массив с результатом подсчёта
for (i; i <= max; i++) {
count[i] = 0;
}
// потом проходим по всему исходному массиву
for (i = 0; i < len; i++) {
// и увеличиваем на единичку ячейки под тем же номером в массиве с результатом подсчёта
count[arr[i]] += 1;
}
// а затем проходим по массиву с результатом
for (i = min; i <= max; i++) {
// пока в очередной ячейке значение больше нуля
while (count[i] > 0) {
// добавляем номер ячейки в исходный массив
arr[j] = i;
// переходим к следующему элементу в исходном массиве
j++;
// уменьшаем на единицу содержимое ячейки в массиве с подсчётом
count[i]--;
}
}
// как всё сделали — возвращаем отсортированный массив
return arr;
};
// исходный массив
let arr = [0,3,5,2,4,5,2,3];
// сортируем его
countingSort(arr,0,5);
// и выводим результат
console.log(arr)
