3622
правки
Изменения
м
Постройка Построение кучи занимает <tex>O(n)</tex>. Почти упорядоченный массив сортировка вставками может отсортировать <tex> O(n)</tex>, но в худшем случае за <tex>O(n^2)</tex> в худшем.
Сам массив же будет выглядеть Массив выглядит следующим образом:
Сам массив же Массив будет выглядеть следующим образом:
→Сложность
== Реализация ==
*<tex>\mathrm{A}</tex> {{---}} массив, который необходимо отсортировать; *<tex>\mathrm{n}</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>. '''fun''' heapsortheapSort(A : '''list <T>'''):
buildHeap(A)
heapSize = A.size
swap(A[0], A[n - 1 - i])
heapSize--
siftDown(A, 0, heap_sizeheapSize)
== Сложность ==
Операция <tex> \mathrm{siftDown} </tex> работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.
Достоинства:
* худшее время работы {{---}} <tex>O(n\log{n})</tex>,
* требует <tex>O(1)</tex> дополнительной памяти.
Недостатки:
* неустойчивая,
* на почти отсортированных данных работает столь же долго, как и на хаотических данных.
== Пример ==
'''JSort''' является модификацией сортировки кучей, которую придумал Джейсон Моррисон (''Jason Morrison'').
Алгоритм частично упорядочивает массив, строя на нем два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо. Затем к массиву применяется
[[Сортировка вставками|сортировка вставками]], которая при почти отсортированных данных работает за <tex>O(n)</tex>.
Достоинства:
*В отличии отличие от сортировки кучей, на почти отсортированных массивах работает быстрее, чем на случайных.
*В силу использования сортировки вставками, которая просматривает элементы последовательно, использование кэша гораздо эффективнее.
Недостатки:
=== Сложность ===
Таким образом в худшем случае сложность JSort является , наихудшая оценка Jsort {{---}} <tex>O(n^2)</tex>.
=== Пример ===
Рассмотрим, массив <tex> A </tex> = <tex> ([1, 2, 8, 15, 17, 20, 31, 32, 30, 2, 3, 5, 10, 11, 24 ) ] </tex>
Построим на этом массиве кучу для минимума:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapW.png|400px]]
|}
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapM.png|400px]]
| [[Файл:HeapWU.png|400px]]
|}
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapMU.png|400px]]
