Подсчитано
Перемещения
Счётчики

  • Считается
  • Только что перемещено
  • На месте

Подробнее о сортировке подсчётом

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

Сортировка подсчётом работает, когда значения — целые числа из небольшого диапазона. Она заводит по счётчику на каждое возможное значение, считает, сколько раз встречается каждое, и по этим количествам точно знает, где место каждого значения. Смотрите, как счётчики заполняются при чтении списка, а затем снова убывают, когда каждое значение перемещается в свой блок, по одному перемещению за раз. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному перемещению. Перетащите ползунок шагов, чтобы перейти в любое место. На полосе между списком и строкой буфера — по одному счётчику на каждое значение. Плитки считают подсчитанные значения, перемещения и счётчики. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

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

  1. Выберите число столбиков и начальный порядок или введите свои целые числа. Попробуйте список с небольшим числом разных значений.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному значению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
  3. Следите за счётчиками: они растут, пока читается список, а затем уменьшаются по мере размещения значений.

Как работает сортировка подсчётом

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

Быстро на малом диапазоне

Сортировка подсчётом читает список дважды и один раз проходит по счётчикам, поэтому её работа растёт как n + k: число значений плюс число счётчиков. Для множества значений из малого диапазона, например баллов за экзамен от 0 до 100 или возрастов, это быстрее любой сортировки сравнениями. При широком диапазоне она тратит время и память на счётчики, которые никому не нужны: трём значениям, разбросанным от 1 до 1 000 000, понадобился бы миллион счётчиков. Это также шаг, который поразрядная сортировка повторяет для каждой цифры.

Часто задаваемые вопросы

Как работает сортировка подсчётом?

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

Когда стоит использовать сортировку подсчётом?

Когда значения — целые числа или их можно в них превратить, а диапазон от наименьшего до наибольшего ненамного больше числа значений: оценки, возраст, короткие коды. Тогда она работает за время, пропорциональное n + k.

Устойчива ли сортировка подсчётом?

Да, если значения перемещаются в порядке списка на следующее свободное место своего блока, как здесь. Именно поэтому поразрядная сортировка может применять её для каждой цифры.

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

Для простых чисел это работает и даже проще. Но реальные данные обычно содержат не только ключ, например имя рядом с каждым баллом, и при записи одних подсчитанных ключей это потеряется. Перемещение самих элементов сохраняет всё, что к ним привязано.

Мои числа куда-нибудь отправляются?

Нет. Сортировка работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор