Изменения
Новая страница: «'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортиров...»
'''Сортировка кучей''', '''пирамидальная сортировка''' (англ. '''Heapsort''') {{---}} алгоритм сортировки, использующий структуру данных [[Двоичная куча|двоичная куча]], который был предложен Дж. Уильямсом в 1964 году. Это нестабильный алгоритм сортировки с гарантированным временем работы <tex>\Theta(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>n - 1</tex>, мы получим отсортированный массив.
== Реализация ==
// Входной массив x, содержащий n элементов.
for i = 0 to n - 1
min = i;
for j = i + 1 to n - 1
if x[j] < x[min]
min = j;
swap(x[i], x[min]);
// Массив x отсортирован
== Пример ==
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 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"| Меняем минимальный и первый элементы местами
|-
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 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"| Меняем минимальный и второй элементы местами
|-
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''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"| Меняем минимальный и третий элементы местами
|-
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''
|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"| Меняем минимальный и четвертый элементы местами
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}
== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]
== Литература ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
== Алгоритм ==
Необходимо отсортировать массив <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>n - 1</tex>, мы получим отсортированный массив.
== Реализация ==
// Входной массив x, содержащий n элементов.
for i = 0 to n - 1
min = i;
for j = i + 1 to n - 1
if x[j] < x[min]
min = j;
swap(x[i], x[min]);
// Массив x отсортирован
== Пример ==
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 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"| Меняем минимальный и первый элементы местами
|-
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 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"| Меняем минимальный и второй элементы местами
|-
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''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"| Меняем минимальный и третий элементы местами
|-
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''
|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"| Меняем минимальный и четвертый элементы местами
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}
== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]
== Литература ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
