Какой алгоритм сортировки я должен использовать в этом сценарии?

Question

Исследователь имеет базу данных из 100 миллионов записей людей. Исследователь хочет изучить распределение имен по другим критериям, таким как знак зодиака, год рождения и т. Д., Поэтому он хочет отсортировать по имени с возможностью дальнейшей сортировки позже.

Какой сорт мне использовать?

A. выбор
Б. быстрый
Кучи
D. вставка
E. слияние

Спасибо!

Answer 1

Это не совсем мой ответ, так как вы сами его достигли, но здесь для лучшей наглядности:

1. Выбор и вставка могут быть исключены, поскольку они имеют O(n^2) среднее время выполнения, которое неМы не собираемся сокращать его на 100 млн. позиций.
2. Исключены динамическая сортировка и быстрая сортировка, поскольку они нестабильны.Эта проблема нуждается в стабильной сортировке, поскольку определение проблемы подразумевает, что при дальнейшей сортировке необходимо сохранить исходный порядок (по имени).
3. Это оставляет только mergesort подходящим кандидатом.

Обновление: Советы по экзамену

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

Такой способ практического мышления делает ИМХО намного проще получить окончательные ответы на некоторые типы экзаменационных вопросов..

Answer 2

Попробуйте сопоставить ваши требования с таблицей сравнения на http://en.wikipedia.org/wiki/Sort_algorithms#Comparison_of_algorithms.

Answer 3

Кто-то опубликовал дубликат, и это будет мой ответ. Поскольку я приложил все усилия, чтобы напечатать все это, я могу также поделиться этим для будущих читателей.

Каждый алгоритм сортировки имеет свои лучшие и худшие варианты использования. Вот как я пытаюсь думать об этом:

• Сортировка выбора: Я редко / никогда не использую сортировку выбора, потому что почти всегда сортировка вставкой выполняет это. Это лучше всего подходит для небольших наборов данных и почти отсортированных списков
• Быстрая сортировка: Ищем лучший средний случай сенарио
• Сортировка кучи: Наилучший возможный наихудший случай
• Сортировка вставки: (см. Выбор)
• Сортировка слиянием: Сортировка слиянием немного медленнее, чем быстрая сортировка, но имеет гарантированное поведение O (n log n). Ключевым моментом здесь является то, что сортировка слиянием гораздо стабильнее, чем быстрая сортировка.

Очевидно, это очень краткий обзор. Вы можете найти гораздо больше информации о Википедии и через поиск в Google, например: «Когда использовать [Вставить алгоритм здесь]»

Надеюсь, это поможет!

Answer 4

Самый эффективный алгоритм сортировки, не будет традиционным.

Поскольку вы сортируете по таким критериям, как год рождения и знак зодиака, я бы сделал "сортировку по стеку" (я только что сделалчто до).

Это будет работать следующим образом.

Создайте структуру данных для каждого возможного отсортированного значения.Давайте использовать год рождения, например.В год рождения будет только ~ 100 различных значений, которые могут быть.

1. Объявите структуру данных для каждого возможного значения года рождения (100 массивов указателей, по одному на каждый год)
2. Переберите каждую запись и поместите указатель на запись в этоммассив.

Когда вы закончили цикл по каждой записи, теперь у вас есть 100 массивов, каждый из которых заполнен записями, которые имеют этот конкретный год рождения.Самое замечательное в этом то, что вы сделали это за O (n) раз, так что это намного быстрее, чем любой другой алгоритм сортировки.Это также работает для знаков зодиака и т.д ...

Думайте вне коробки.Этот подход очень полезен при сортировке большого набора данных (n) с возможными значениями (m), где m << n. </p>

Answer 5

Если вы хотите получить гистограмму, я бы не сортировал данные. Я бы просто просмотрел все данные, считая все интересующие комбинации. Это операция O (N).

Сортировка данных в первую очередь вряд ли улучшит скорость. Это операция O (N * log (N)).

---

Если бы вы хотели отсортировать все записи, я бы использовал Collection.sort () с пользовательским компаратором, который имеет все поля, которые нужно сравнить. Вам нужно будет загрузить все записи в память, что займет несколько ГБ, но как только вы это сделаете, все должно быть довольно быстро.

Единственный способ сделать это быстрее - отфильтровать критерии. Если вы сделаете это, я бы создал коллекцию, в которой есть копия записей, представляющих интерес, и отсортировал бы ее.