Сортировка подсчетом сложных объектов

Эта статья находится в разработке!

Иногда бывает очень желательно применить быстрый алгоритм сортировки подсчетом для упорядочивания набора каких-либо "сложных" данных. Под "сложными объектами" здесь подразумеваются структуры, содержащие в себе несколько полей. Одно из них мы выделим и назовем ключом, сортировка будет идти именно по нему (предполагается, что значения, принимаемые ключом - целые числа в диапазоне от [math]0[/math] до [math]k-1[/math]).

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

Использование списков

Пусть далее исходная последовательность из [math]n[/math] структур хранится в массиве [math]A[/math], а отсортированная - в массиве [math]P[/math] с индексами от [math]0[/math] до [math]k-1[/math].

Сделаем из каждой ячейки массива [math]B[/math] список, в который будем добавлять структуры с одинаковыми ключами.

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

Подсчет числа различных ключей

Здесь исходная последовательность из [math]n[/math] структур хранится в массиве [math]A[/math], а отсортированная - в массиве [math]B[/math] того же размера. Кроме того используется вспомогательный массив [math]P[/math] с индексами от [math]0[/math] до [math]k-1[/math].

• Пройдем по исходному массиву [math]A[/math] и запишем в [math]P[i][/math] количество структур, ключ которых равен [math]i[/math]. Это можно сделать за [math] O(n)[/math].
• Условно разобьем массив [math]B[/math] на [math]k[/math] блоков, длина каждого из которых равна соответственно [math]P[1][/math], [math]P[2][/math], ..., [math]P[k][/math].
• Теперь массив [math]P[/math] нам больше не нужен. Превратим его в массив, хранящий в [math]P[i][/math] сумму элементов от [math]0[/math] до [math]i-1[/math] старого массива [math]P[/math]. Это делается за один пробег по массиву [math]P[/math], то есть имеет сложность [math] O(k)[/math].
• Произведем саму сортировку. Еще раз пройдем по исходному массиву [math]A[/math] и для всех [math]i \in [0, n-1][/math] будем помещать структуру [math]A[i][/math] в массив [math]B[/math] на место [math]P[A[i].key]-1[/math]. Здесь [math]A[i].key[/math] — это ключ структуры, находящейся в массиве [math]A[/math] на [math]i[/math]-том месте. Затем увеличим [math]P[A[i].key][/math] на единицу.

Таким образом после завершения алгоритма в [math]B[/math] будет содержаться исходная последовательность в отсортированном виде (так как блоки расположены по возрастанию соответствующих ключей).

Стоит также отметить, что эта сортировка является устойчивой, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в каком просматривались в исходном массиве [math]A[/math].

Источники

• Википедия — Сортировка подсчетом
• Wikipedia — Counting sort
• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 224-226.