Какой алгоритм сортировки является лучшим в следующих случаях?

Question

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

1) Сортировка набора сопоставимых элементов : я бы сказал, сортировка кучи / слияния, потому что они имеют O (n logn) сложность времени во всех случаях. Или быстрая сортировка?

2) Сортировка набора элементов, состоящих из 32-битных цифр : Может быть, радикальная сортировка, но я не уверен.

3) Сортировка набора сопоставимых элементов при условии, что перестановки стоят дорого, а сравнения - не : Я полагаю, будет сортировка выбора, потому что у вас есть много сравнений, но только (n-1) движений.

4) Сортировка набора сопоставимых элементов при условии, что вы знаете, что первые (n-m) элементы уже отсортированы и только последние m элементов не отсортированы. Существует ли процесс O (m log n) или O (n log m)? : я бы сказал, сортировка вставкой из-за этого https://www.toptal.com/developers/sorting-algorithms/,, но я не имею понятия об остальной части вопрос.

5) Сортировка набора сопоставимых элементов при условии, что решение требуется в определенный срок, который в будущем будет меньше n ^ 2 операций : поскольку наихудший случай быстрой сортировки равен n ^ 2, я бы выбрал сортировку слиянием или кучей.

6) Сортировка набора сопоставимых элементов, но процесс должен быть стабильным : это должна быть сортировка слиянием, поскольку все остальные алгоритмы нестабильны.

Answer 1

Ну, есть несколько неправильных вопросов.

1-й: Сортировка набора сопоставимых объектов: Если я не ошибаюсь, то каждый объект сопоставим.Исходные строки могут быть отсортированы без сопоставления, но это особый случай.

Я выберу быструю сортировку со случайным перемешиванием, чтобы избежать наихудшего сценария.Попробуйте Doubling ratio-test на Mergesort и QuickSort, вы заметите, что с увеличением размера слияние станет медленнее.Однако Mergesort может быть улучшен с помощью вставки-сортировки в рекурсивных вызовах.

2: Это то же самое, что сортировка строк, и это полностью зависит от того, как вы хотите их отсортировать?По первой цифре, последняя цифра или все должны быть отсортированы?Так что для них существует множество алгоритмов: MSD , LSD , Quick-3wayString сортирует .

4: Сортировка набора сопоставимых элементов при условии, что вы знаете, что первые (nm) элементы уже отсортированы, и только последние m элементов не отсортированы.Существует ли процесс O (m log n) или O (n log m): Можно ли использовать сортировку вставкой в ​​базовом случае сортировки слиянием , чтобы всегда разбивал массив надве половины (нм) и (м + 1 - н)?Так как сортировка вставкой прервет цикл после выполнения только n сравнения, а другая половина будет отсортирована по сортировке слиянием в NlogN , и вы получите верхнюю границу как NlogN .

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

6: Да, если вам нужно выбрать один из этих алгоритмов, тогда Mergesort - единственный.