Алгоритм сортировки по высоте 1,14 миллиарда человек!

Question

Это вопрос интервью: учитывая, что население Индии составляет 1,14 миллиарда человек, какой самый эффективный / эффективный алгоритм сортировки можно использовать для сортировки их по высоте? (Данные о высотах вам доступны).

Answer 1

O (п):

Если высоты можно округлить до ближайшего мм, то вы можете вычислить гистограмму высот и распечатать счетчики в каждой группе гистограмм по порядку. Ожидаемый объем оперативной памяти составляет всего несколько КБ для примерно 2000 32-разрядных целых.

Answer 2

Поскольку диапазон возможных высот довольно мал, я рекомендую:

1. Выразите все высоты в миллиметрах.
2. Выполните один проход по данным, вычисляя минимальную и максимальную высоты.
3. Распределите бункеры на большую высоту между минимальным и максимальным.
4. Сделайте второй проход по данным, добавив людей в соответствующие корзины.

Это два прохода по набору данных плюс распределение бинов. О (п).

Answer 3

Я предполагаю, что интервьюер предполагает, что количество различных высот значительно меньше, чем количество людей, что означает, что сортировка с подсчетом будет уместной, которая имеет сложность шага наихудшего случая: Θ(n+k), где n - количество людей, а k - количество высот.

Поскольку сортировка с подсчетом не является сортировкой сравнения, типичная нижняя граница Ω(n×log n) не применяется, что, вероятно, было тем, что интервьюер действительно достиг.

Answer 4

Другой вариант линейного времени для ограниченных числовых данных - radix sort , который является просто специализированной числовой версией bin sort .