Про один специальный случай pigeonhole сортировки

Pigeonhole сортировка — это такой старый способ несравнивающей сортировки, в котором элементы входного массива «разбрасываются» по массивам, соответствующим домену индекса сортировки, а потом собираются вместе в нужном порядке.

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

Нет никакой причины использовать даже самую эффективную сравнивающую сортировку, нам достаточно создать три массива: по одному на каждое возможное значение приоритета, и за один проход «разложить» значения исходного массива по этим трем. Потом тривиальнейшим образом сконкатенировать их в один — и все.

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

Допустим, мы распараллелили какую-то сложную задачу так, что ее по частям обрабатывает множество процессов. Каждый процесс имеет свой идентификатор Id, допустим даже, при N процессов это будут натуральные числа из [1..N]. Результаты своей работы они сообщают через очередь сообщений в виде кортежей (Id, Res), и конечно не гарантируют правильность их последовательности. После того, как все процессы отчитаются, нам надо будет эту очередь по Id упорядочить.

В этом случае у нас существует взаимно-однозначное отображение индекса отсортированного массива и идентификатора процесса. Нам достаточно просто сформировать массив A длины N и «разложить» значения из очереди так что A[Id-1] = (Id, Res). Тот же pigeonhole, только в каждой клетке может сидеть один и только один голубь.

Отображение не обязательно должно быть тривиальным. Это может быть преобразование из даты в день года для сортировки каких-нибудь ежедневных отчетов или какой-то естественный способ нумерации периодики. Главное, что когда каждому значению неотсортированного массива соответствует, тем или иным способом, индекс в отсортированном массиве, никакой сортировки per se и не требуется.

Это все очень просто, но почему-то не общеизвестно. Цель этой заметки — напомнить читателям про несравнивающую сортировку и ее прелести в ограниченном, конечно же, но не пустом подмножестве приложений.

Автор: akalenuk

Источник ^[1]