Сортировка кучей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это нестабильный алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.
+
'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]]. Это неустойчивый алгоритм сортировки с временем работы <tex>O(n\log{n})</tex> , где <tex>n</tex> {{---}} количество элементов для сортировки, и использующий <tex>O(1)</tex> дополнительной памяти.
  
 
== Алгоритм ==
 
== Алгоритм ==
Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру '''sift_down(0)''', предварительно уменьшив <tex>heap\_size</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>heap\_size</tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.
+
Необходимо отсортировать массив <tex>A</tex>, размером <tex>n</tex>. Построим на базе этого массива за <tex>O(n)</tex> невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с <tex>A[n - 1]</tex>, он встанет на свое место. Далее вызовем процедуру <tex>sift\_down(0)</tex>, предварительно уменьшив <tex>heap\_size</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>heap\_size</tex> не станет равен <tex>1</tex>, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.
  
 
== Реализация ==
 
== Реализация ==
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; '''build_heap(A)''' - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; '''sift_down(A, i, len)''' {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.
+
<tex>A</tex> {{---}} массив, который необходимо отсортировать; <tex>n</tex> {{---}} количество элементов в нем; <tex>build\_heap(A)</tex> - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; <tex>sift\_down(A, i, len)</tex> {{---}} процедура, которая просеивает вниз элемент <tex>A[i]</tex> в куче из <tex>len</tex> элементов, находящихся в начале массива <tex>A</tex>.
 
<pre>
 
<pre>
 
heapsort(A)
 
heapsort(A)
Строка 17: Строка 17:
  
 
== Сложность ==
 
== Сложность ==
Операция '''sift_down''' работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.
+
Операция <tex>sift\_down</tex> работает за <tex>O(\log{n})</tex>. Всего цикл выполняется <tex>(n - 1)</tex> раз. Таким образом сложность сортировки кучей является <tex>O(n\log{n})</tex>.
  
  
Строка 24: Строка 24:
 
{|align="right"
 
{|align="right"
 
  |-valign="top"
 
  |-valign="top"
  |[[Файл:Документ1.png|120px|thumb|Строим кучу]]
+
  |[[Файл:heap1.png|180px|thumb|Строим кучу]]
  |[[Файл:Документ2.png|120px|thumb|Первый проход]]
+
  |[[Файл:heap2.png|180px|thumb|Первый проход]]
  |[[Файл:Документ3.png|120px|thumb|Строим новую кучу]]
+
  |[[Файл:heap3.png|180px|thumb|Строим новую кучу]]
 
  |-
 
  |-
  |[[Файл:Документ4.png|120px|thumb|Второй проход]]
+
  |[[Файл:heap4.png|180px|thumb|Второй проход]]
  |[[Файл:Документ5.png|120px|thumb|Третий проход]]
+
  |[[Файл:heap5.png|180px|thumb|Третий проход]]
  |[[Файл:Документ6.png|120px|thumb|Четвертый проход]]
+
  |[[Файл:heap6.png|180px|thumb|Четвертый проход]]
 
  |}
 
  |}
  

Версия 16:31, 10 июня 2012

Сортировка кучей, пирамидальная сортировка (англ. Heapsort) — алгоритм сортировки, использующий структуру данных двоичная куча. Это неустойчивый алгоритм сортировки с временем работы [math]O(n\log{n})[/math] , где [math]n[/math] — количество элементов для сортировки, и использующий [math]O(1)[/math] дополнительной памяти.

Алгоритм

Необходимо отсортировать массив [math]A[/math], размером [math]n[/math]. Построим на базе этого массива за [math]O(n)[/math] невозрастающую кучу. Так как по свойству кучи максимальный элемент находится в корне, то, поменявшись его местами с [math]A[n - 1][/math], он встанет на свое место. Далее вызовем процедуру [math]sift\_down(0)[/math], предварительно уменьшив [math]heap\_size[/math] на [math]1[/math]. Она за [math]O(\log{n})[/math] просеет [math]A[0][/math] на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с [math]A[0][/math] по [math]A[n - 2][/math], а элемент [math]A[n-1][/math] находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с [math]A[n - 1][/math], а с [math]A[n-2][/math]. Делая аналогичные действия, пока [math]heap\_size[/math] не станет равен [math]1[/math], мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

Реализация

[math]A[/math] — массив, который необходимо отсортировать; [math]n[/math] — количество элементов в нем; [math]build\_heap(A)[/math] - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; [math]sift\_down(A, i, len)[/math] — процедура, которая просеивает вниз элемент [math]A[i][/math] в куче из [math]len[/math] элементов, находящихся в начале массива [math]A[/math].

heapsort(A)
  build_heap(A);
  heap_size = A.size;
  for i = 0 to n - 2
    swap(A[0], A[n - 1 - i]);
    heap_size--;
    sift_down(A, 0, heap_size);

Сложность

Операция [math]sift\_down[/math] работает за [math]O(\log{n})[/math]. Всего цикл выполняется [math](n - 1)[/math] раз. Таким образом сложность сортировки кучей является [math]O(n\log{n})[/math].


Пример

Строим кучу
Первый проход
Строим новую кучу
Второй проход
Третий проход
Четвертый проход

Пусть дана последовательность из [math]5[/math] элементов [math]3, 2, 4, 1, 5[/math].

Массив Описание шага
5 3 4 1 2 Строим кучу из исходного массива
Первый проход
2 3 4 1 5 Меняем местами первый и последний элементы
4 3 2 1 5 Строим кучу из первых четырех элементов
Второй проход
1 3 2 4 5 Меняем местами первый и четвертый элементы
3 1 2 4 5 Строим кучу из первых трех элементов
Третий проход
2 1 3 4 5 Меняем местами первый и третий элементы
2 1 3 4 5 Строим кучу из двух элементов
Четвертый проход
1 2 3 4 5 Меняем местами первый и второй элементы
1 2 3 4 5 Массив отсортирован


Ссылки

Литература

  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4