Cортировка подсчётом: как работает сортировка без сравнений

Cортировка подсчётом: как работает сортировка без сравнений

Надо просто посчитать, сколько раз встречается каждый элемент

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

Сортировка — это процесс, когда какой-то набор чисел выстраивают по возрастанию или убыванию. Сортировать можно просто числа или целые таблицы с кучей значений. Когда вы сортируете что-то в Экселе или открываете список контактов в телефоне, работает какой-то алгоритм сортировки.

В обычных сортировках мы разными способами сравниваем элементы массива между собой. Но есть пара сортировок, в которых нет сравнений, но массив всё равно выстраивается по порядку. Рассказываем, как работает такая магия на примере сортировки подсчётом.

Сортировка подсчётом лучше всего работает при таких условиях:

  • массив очень большой — значений много;
  • эти значения лежат в известном нам диапазоне (например, это диапазон работы какого-то датчика);
  • диапазон намного меньше, чем размер массива, то есть единицы данных могут повторяться.

Принцип работы

Главная идея алгоритма — посчитать, сколько раз встречается каждый элемент в массиве, а потом заполнить исходный массив результатами этого подсчёта. Для этого нам нужен вспомогательный массив, где мы будем хранить результаты подсчёта. Даже если нам надо отсортировать миллион чисел, мы всё равно знаем диапазон этих чисел заранее, например, от 1 до 100. Это значит, что во вспомогательном массиве будет не миллион элементов, а сто. 

В общем виде всё работает так:

  1. Мы создаём вспомогательный массив и на старте заполняем его нулями.
  2. Проходим по всему исходному массиву и смотрим очередное значение в ячейке.
  3. Берём содержимое этой ячейки и увеличиваем на единицу значение вспомогательного массива под этим номером. Например, если мы встретили число 5, то увеличиваем на единицу пятый элемент вспомогательного массива. Если встретили 13 — тринадцатый.
  4. После цикла во вспомогательном массиве у нас хранятся данные, сколько раз встречается каждый элемент.
  5. Теперь мы проходим по вспомогательному массиву, и если в очередной ячейке лежит что-то больше нуля, то мы в исходный массив столько же раз отправляем номер этой ячейки. Например, в первой ячейке вспомогательного массива лежит число 7. Это значит, что в исходный массив мы отправляем единицу 7 раз подряд.

В итоге мы получаем отсортированный массив без сравнения элементов. Вот как это выглядит на практике:

Cортировка подсчётом: как работает сортировка без сравнений

Зачем нужна эта сортировка

Допустим, у нас есть какой-то прибор, который выдаёт результаты в определённом диапазоне, например показывает сейсмоактивность этом регионе в диапазоне от 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)

Визуализация сортировки:

Валерий Макаров

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Екатерина Череповицына

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Универсальная аналитическая машина

Она может предсказать что угодно, если правильно её настроить.

medium
Как сделать колесо фортуны на сайте
Как сделать колесо фортуны на сайте

Достаточно одного скрипта и немного CSS

medium
Делаем эффектную фотогалерею на сайте
Делаем эффектную фотогалерею на сайте

Красивый трёхмерный виджет с несложным кодом

hard
Программируем скринсейвер для Илона
Программируем скринсейвер для Илона

Анимация движения звёзд на JavaScript.

medium
Как убрать что угодно на любом сайте
Как убрать что угодно на любом сайте

Самый популярный приём разработчиков.

easy
Как сохранить JSON на сервере
Как сохранить JSON на сервере

И отдать его обратно по запросу.

medium
Что означает ошибка OverflowError: math range error
Что означает ошибка OverflowError: math range error

Это ошибка переполнения из-за математических операций

easy
Создаём CSS-сетку нужного размера

Рассказываем, как сделать шаблон любой страницы.

medium
Как утащить простой сайт за 5 минут
Как утащить простой сайт за 5 минут

Например, чтобы научиться делать так же

easy
Как очень быстро и яростно добавить музыкальный трек на страницу
Как очень быстро и яростно добавить музыкальный трек на страницу

Всё для семьи

easy
medium