Как отсортировать (млн / млрд / ...) целых чисел?

Question

Иногда интервьюеры спрашивают, как отсортировать 32 миллиона бит / миллион (например, здесь и здесь ). Я предполагаю, что они ожидают, что кандидаты сравнивают сортировку O (N Log (N)) с сортировкой по основанию. Для миллиона целых чисел O (N Log (N)) сортировка, вероятно, лучше, но для миллиарда они, вероятно, совпадают. Имеет ли это смысл?

Answer 1

Если вы получили такой вопрос, они не ищут ответа.То, что они пытаются сделать, это увидеть, как вы решаете проблему.Вы прыгаете прямо или задаете вопросы о требованиях проекта?

Один вопрос, который вам лучше задать, это: «Насколько оптимального решения требует проблема?»Может быть, записи типа «пузырь», хранящиеся в файле, достаточно хороши, но вы должны спросить.Задайте вопросы о том, что, если ввод изменится на 64-битные числа, процесс сортировки должен быть легко обновлен?Спросите, как долго программист должен разрабатывать программу.

Эти типы вопросов показывают мне, что кандидат достаточно мудр, чтобы увидеть, что есть нечто большее, чем просто сортировка чисел.

Answer 2

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

Answer 3

Как сказал aaaa bbbb , это зависит от ситуации. Вы будете задавать вопросы о требованиях проекта. Например, если они хотят посчитать возраст сотрудников, вы, вероятно, используете Подсчет сортировки , я могу отсортировать данные в памяти. Но когда данные полностью случайны, вы, вероятно, используете внешнюю сортировку . Например, вы можете разделить данные исходного файла на разные файлы, каждый файл имеет уникальный диапазон (File1 от 0-1m, File2 от 1m + 1 - 2m и т. Д.), Затем вы сортируете каждый отдельный файл и, наконец, объединить их в новый файл.

Answer 4

Использовать битовую карту.Вам нужно около 500 Мб для представления всего 32-битного целочисленного диапазона.Для каждого целого числа в данном массиве просто установите coresponding бит.Затем просто отсканируйте свою битовую карту слева направо и отсортируйте целочисленный массив.

Answer 5

Это зависит от структуры данных, в которой они хранятся. Radix-сортировка превосходит N-log-N-сортировку при довольно небольших размерах задач, если входные данные находятся в связанном списке, потому что для этого не нужно выделять пустую память, и если вы можете позволить себе выделить буфер для очистки размера входных данных в начале сортировки, то же самое относится и к массивам. Это действительно только неправильный выбор (для целочисленных ключей), когда у вас очень ограниченное дополнительное пространство для хранения, и ваш ввод находится в массиве.

Я бы ожидал, что точка кроссовера будет значительно ниже миллиона независимо от этого.