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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 21: Строка 21:
  
 
== Пример ==
 
== Пример ==
'''''РАЗДЕЛ В РАЗРАБОТКЕ'''''
 
  
 +
{|align="right"
 +
|-valign="top"
 +
|[[Файл:Документ1.jpg|120px|right|thumb|Строим кучу]]
 +
|[[Файл:Документ2.jpg|120px|right|thumb|Первый проход]]
 +
|[[Файл:Документ3.jpg|120px|right|thumb|Второй проход]]
 +
|-
 +
|[[Файл:Документ4.jpg|120px|right|thumb|Четвертый проход]]
 +
|[[Файл:Документ5.jpg|120px|right|thumb|Пятый проход]]
 +
|[[Файл:Документ6.jpg|120px|right|thumb|Массив отсортирован]]
 +
|}
  
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.
+
Пусть дана последовательность из <tex>5</tex> элементов <tex>3, 2, 4, 1, 5</tex>.
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 30: Строка 39:
 
!style="background-color:#EEE"| Описание шага
 
!style="background-color:#EEE"| Описание шага
 
|-
 
|-
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''
+
|style="background-color:#FFF;padding:2px 10px"| 5 3 4 1 2
 +
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из исходного массива
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3
+
|colspan=3|''Первый проход''
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1'''  
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3
+
|style="background-color:#FFF;padding:2px 10px"| '''2''' 3 4 1 '''5'''
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами
+
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и последний элементы  
 
|-
 
|-
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
+
|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"| 1 5 4 '''2''' 3
+
|colspan=3|''Второй проход''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2'''  
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3
+
|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"| Меняем местами первый и четвертый элементы  
 
|-
 
|-
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
+
|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"| 1 2 4 5 '''3'''
+
|colspan=3|''Третий проход''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3'''  
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''
+
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 '''3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами
+
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и третий элементы  
 
|-
 
|-
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
+
|style="background-color:#FFF;padding:2px 10px"| '''2''' 1 3 4 5
 +
|style="background-color:#FFF;padding:2px 10px"| Строим кучу из двух элементов
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''
+
|colspan=3|''Четвертый проход''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4'''  
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''
+
|style="background-color:#FFF;padding:2px 10px"| '''1''' '''2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами
+
|style="background-color:#FFF;padding:2px 10px"| Меняем местами первый и второй элементы
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5

Версия 22:44, 3 июня 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], он встанет на свое место. Далее вызовем процедуру sift_down(0), предварительно уменьшив [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] — количество элементов в нем; build_heap(A) - процедура, которая строит из передаваемого массива невозрастающую кучу в этом же массиве; sift_down(A, i, len) — процедура, которая просеивает вниз элемент [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);

Сложность

Операция sift_down работает за [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