Как отсортировать оперативное использование алгоритма сортировки слиянием?
Я знаю, что вопрос не слишком конкретен.
Все, что я хочу, является кем-то, чтобы сказать мне, как преобразовать нормальную сортировку слиянием в оперативную сортировку слиянием (или сортировку слиянием с постоянным дополнительным пространством наверху).
Все, что я могу найти (в сети) является страницами, говоря, что "это слишком сложно" или "из объема этого текста".
Единственные известные способы объединиться оперативный (без любого дополнительного пространства) слишком сложны, чтобы быть уменьшенными до практической программы. (взятый отсюда)
Даже если это слишком сложно, каково фундаментальное понятие того, как сделать сортировку слиянием оперативной?
3 ответа
Это действительно непросто или эффективно, и я предлагаю вам не делать этого, если вам действительно не нужно (и вам, вероятно, не нужно, если это не домашнее задание, поскольку применение слияния на месте в основном теоретическое). Разве вы не можете использовать быструю сортировку вместо этого? Quicksort в любом случае будет быстрее с помощью нескольких более простых оптимизаций, а его дополнительная память составляет O (log N) .
В любом случае, если вы должны это сделать, вы должны. Вот что я нашел: один и два . Я не знаком с сортировкой слияния на месте, но похоже, что основная идея состоит в том, чтобы использовать ротацию для облегчения слияния двух массивов без использования дополнительной памяти.
Обратите внимание, что это медленнее даже классической сортировки слиянием, которой нет на месте.
Критическим этапом является установка самого слияния на месте. Это не так сложно, как утверждают эти источники, но при попытке вы что-то теряете.
Рассмотрим один шаг слияния:
[... list- sorted .. . | x ... list- A ... | y ... list- B ...]
Мы знаем, что отсортированная последовательность меньше всего остального, что x меньше, чем все остальное в A , и что y меньше, чем все остальное в B . В случае, когда x меньше или равно y , вы просто перемещаете указатель на начало A на единицу. В случае, когда y меньше, чем x , вам нужно перетасовать y за весь A в отсортировано . Этот последний шаг и делает это дорого (кроме вырожденных случаев).
Как правило, дешевле (особенно когда массивы фактически содержат только отдельные слова на элемент, например, указатель на строку или структуру) уступить некоторое пространство времени и получить отдельный временный массив, который вы сортируете взад и вперед между ними.
В этом документе, включая «большой результат», описывается несколько вариантов сортировки слиянием на месте (PDF):
http: // citeseerx .ist.psu.edu / viewdoc / download? doi = 10.1.1.22.5514 & rep = rep1 & type = pdf
Сортировка на месте с меньшим количеством ходов
Юрки Катаянен, Томи А. Пасанен
Показано, что массив из n элементов может быть отсортирован с использованием O (1) дополнительного пространства, O (n log n / log log n) перемещений элементов и n log 2 n + O (n log log n) сравнений. Это первый алгоритм сортировки на месте, требующий o (n log n) перемещений в худшем случае , гарантируя при этом O (n log n) сравнений. , но из-за постоянных факторов алгоритм представляет преимущественно теоретический интерес.
Думаю, это тоже актуально. У меня есть распечатка, которую мне передал коллега, но я ее не читал. Кажется, это охватывает основную теорию, но я недостаточно знаком с этой темой, чтобы судить, насколько исчерпывающе:
http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681
Оптимально Стабильное слияние
Антониос Симвонис
В этой статье показано, как стабильно слить две последовательности A и B размеров m и n, m ≤ n, соответственно, с O (m + n ) присваивания, O (mlog (n / m + 1)) сравнений и использование только постоянного количества дополнительного места.Этот результат соответствует всем известным нижним границам ...