Лучший алгоритм сортировки для частично отсортированной последовательности?

Question

Я должен ответить на следующий вопрос:

Какой алгоритм сортировки рекомендуется, если первая n-м деталь
уже отсортировано, а оставшаяся часть m не отсортирована? Существуют ли алгоритмы, которые берут O (n log m) сравнений? Что насчет O (m log n) сравнений?

Я просто не могу найти решение.

Моей первой идеей была сортировка вставкой, потому что O (n) для почти отсортированной последовательности. Но так как мы не знаем размер m, вполне вероятно, что время выполнения будет O (n ^ 2), хотя последовательность уже наполовину отсортирована, не так ли?

Тогда я решил, что perhabs его быстрая сортировка, потому что он требует (сумма от k = 1 до n) сравнений Cavg (1-m) + Cavg (n-m). Но после игнорирования n-m части последовательности оставшаяся последовательность будет 1-m в быстрой сортировке, а не m.

Объединение сортировки и сортировки кучи должно иметь время выполнения O (m log m) для оставшейся последовательности m, я бы сказал.

Кто-нибудь имеет идею или может дать мне совет?

Привет

Answer 1

Вы пробовали сортировать оставшуюся часть m отдельно как O(m log (m)) сложность (с любым алгоритмом, который вам нравится: MergeSort, HeapSort, QuickSort, ...), а затем объединить эта часть с отсортированной частью с использованием MergeSort (Вам даже не нужно будет полностью реализовывать MergeSort - просто один проход его тела внутреннего цикла для объединения двух отсортированных последовательностей)?

Это приведет кO(m*log(m) + n + m) = O(m*log(m) + n) сложность.Я не верю, что можно найти лучшую асимптотическую сложность на одноядерном процессоре.Хотя для слияния массива результатов потребуется дополнительная O(n+m) память.

Answer 2

Какой алгоритм сортировки лучше всего работает с в основном отсортированными данными?

Звучит как вставка и пузырь, это хорошо. Вы можете реализовать столько, сколько захотите, а затем протестировать, чтобы увидеть, какие операции выполняются быстрее / меньше, предоставляя им частично отсортированные данные.