Редактирование: Сортировка кучей
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 2: | Строка 2: | ||
== Алгоритм == | == Алгоритм == | ||
− | Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> кучу для максимума. Так как максимальный элемент находится в корне, то если поменять его местами с <tex>A[n - 1]</tex>, он встанет на | + | Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> кучу для максимума. Так как максимальный элемент находится в корне, то,если поменять его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру <tex> \mathrm{siftDown(0)} </tex>, предварительно уменьшив <tex> \mathrm{heapSize} </tex> на <tex>1</tex>. Она за <tex>O(\log{n})</tex> просеет <tex>A[0]</tex> на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с <tex>A[0]</tex> по <tex>A[n - 2]</tex>, а элемент <tex>A[n-1]</tex> находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с <tex>A[n - 1]</tex>, а с <tex>A[n-2]</tex>. Делая аналогичные действия, пока <tex> \mathrm{heapSize} </tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив. |
== Реализация == | == Реализация == | ||
*<tex>\mathrm{A}</tex> {{---}} массив, который необходимо отсортировать | *<tex>\mathrm{A}</tex> {{---}} массив, который необходимо отсортировать | ||
− | *<tex>\mathrm{n}</tex> {{---}} количество элементов в | + | *<tex>\mathrm{n}</tex> {{---}} количество элементов в нем |
*<tex> \mathrm{buildHeap(A)} </tex> {{---}} процедура, которая строит из передаваемого массива кучу для максимума в этом же массиве | *<tex> \mathrm{buildHeap(A)} </tex> {{---}} процедура, которая строит из передаваемого массива кучу для максимума в этом же массиве | ||
*<tex> \mathrm{siftDown(A, i, len)} </tex> {{---}} процедура, которая просеивает вниз элемент <tex> \mathrm{A[i]} </tex> в куче из <tex> \mathrm{len} </tex> элементов, находящихся в начале массива <tex> \mathrm{A} </tex> | *<tex> \mathrm{siftDown(A, i, len)} </tex> {{---}} процедура, которая просеивает вниз элемент <tex> \mathrm{A[i]} </tex> в куче из <tex> \mathrm{len} </tex> элементов, находящихся в начале массива <tex> \mathrm{A} </tex> | ||
Строка 37: | Строка 37: | ||
|[[Файл:heap4.png|155px|thumb|Второй проход]] | |[[Файл:heap4.png|155px|thumb|Второй проход]] | ||
|[[Файл:heap5.png|155px|thumb|Третий проход]] | |[[Файл:heap5.png|155px|thumb|Третий проход]] | ||
− | |[[Файл:heap6.png|155px|thumb| | + | |[[Файл:heap6.png|155px|thumb|Четвертый проход]] |
|} | |} | ||
Строка 55: | Строка 55: | ||
|- | |- | ||
|style="background-color:#FFF;padding:2px 10px"| '''4''' 3 2 1 5 | |style="background-color:#FFF;padding:2px 10px"| '''4''' 3 2 1 5 | ||
− | |style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых | + | |style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых четырех элементов |
|- | |- | ||
|colspan=3|''Второй проход'' | |colspan=3|''Второй проход'' | ||
|- | |- | ||
|style="background-color:#FFF;padding:2px 10px"| '''1''' 3 2 '''4''' 5 | |style="background-color:#FFF;padding:2px 10px"| '''1''' 3 2 '''4''' 5 | ||
− | |style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и | + | |style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и четвертый элементы |
|- | |- | ||
|style="background-color:#FFF;padding:2px 10px"| '''3''' 1 2 4 5 | |style="background-color:#FFF;padding:2px 10px"| '''3''' 1 2 4 5 | ||
− | |style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых | + | |style="background-color:#FFF;padding:2px 10px"| Строим кучу из первых трех элементов |
|- | |- | ||
|colspan=3|''Третий проход'' | |colspan=3|''Третий проход'' | ||
Строка 73: | Строка 73: | ||
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов | |style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов | ||
|- | |- | ||
− | |colspan=3|'' | + | |colspan=3|''Четвертый проход'' |
|- | |- | ||
|style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5 | |style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5 | ||
Строка 87: | Строка 87: | ||
= JSort = | = JSort = | ||
'''JSort''' является модификацией сортировки кучей, которую придумал Джейсон Моррисон (''Jason Morrison''). | '''JSort''' является модификацией сортировки кучей, которую придумал Джейсон Моррисон (''Jason Morrison''). | ||
− | Алгоритм частично упорядочивает массив, строя на | + | Алгоритм частично упорядочивает массив, строя на нем два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо. Затем к массиву применяется |
[[Сортировка вставками|сортировка вставками]], которая при почти отсортированных данных работает за <tex>O(n)</tex>. | [[Сортировка вставками|сортировка вставками]], которая при почти отсортированных данных работает за <tex>O(n)</tex>. | ||
Строка 99: | Строка 99: | ||
Построим кучу для минимума на этом массиве. | Построим кучу для минимума на этом массиве. | ||
Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи. | Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи. | ||
− | Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть кучей для максимума и быть "зеркальной" к массиву, то есть чтобы | + | Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть кучей для максимума и быть "зеркальной" к массиву, то есть чтобы ее корень соответствовал последнему элементу массива. |
К получившемуся массиву применим сортировку вставками. | К получившемуся массиву применим сортировку вставками. | ||