Улучшенные методы сортировки.

Быстрая сортировка.( Сортировка Хоара) данный алгоритм называется сортировка с разделением, поэтому считается улучшенным методом. Самый простой случай быстрой сортировки , когда n элементов массива расположены в обратном порядке. Данные можно сортировать выполнив n/2 шагов, если сначала поменять местами правые и левые элементы и так далее, двигаясь с двух сторон к середине.

Принцип работы быстрой сортировки: Данные формируются по возрастанию.

1.Сначала среди элементов выбирается некоторый элемент x, относительно которого будут проводиться последовательные действия.

2.Двигаясь с лева на право, ищем элемент меньше x, a<x.

3.просматриваем массив в правой стороне , пока не найдем элемент

4. далее эти два элемента меняются местами.

5.процесс повторяется пока данные элементы не встретятся в центре массива.

6.после просмотра массив делится на две части левая с элементами меньше или равно х. правая с элементами больше или равно х.

7.процессс повторяется, но уже с первой частью данных , а потом со второй.

8.процесс повторяется до тех пор, пока данные не будут отсортированы.

Способы выбора элемента х.

Это может быть центральный элемент последовательности или первый элемент.

Пример: 34,17,45,9,6,18,12,14,37,49,5. Выбираем элемент х=18. Из левой части выбираем элемент, который больше 18(34), из правой части элемент, который меньше 18(5). Меняем их местами: 5,17,45,9,6,18,12,14,37,49,34. 5,17,14,9,6,18,12,45,37,49,34. 5,(17),14.9,(6),12|18,(45),37,49,(34).

Имеется последовательность 4,12,32,7,15,24,70,14,36. Отсортировать по возрастанию.

пирамидальная сортировка.

Это улучшенный алгоритм простым выбором. Данное улучшение было разработано Р.Флойдом. он предложил перестраивать линейный массив в пирамиду, которая моделирует бинарное дерево. В таком дереве два нижних соседних элемента всегда имею т один элемент, который расположен над ними на один уровень выше, минимальный элемент ищется среди этих двух элементов.

Работа метода.

Сначала производится просеивание – это первая часть алгоритма, а затем осуществляется основная сортировка. Первая часть необходима для преобразования исходного массива в пирамиду, в которой каждый верхний элемент опирается на два меньших элемента. Это просеивание, так как данная операция напоминает процесс разделения на смеси в соответствии с их размером.

A[1]
A[2]				A[3]
A[4]		A[5]			A[6]		A[7]
A[8]	A[9]	A[10]	A[11]		A[12]	A[13]	A[14]	A[15]

Любой элемент a[i] где 1<=i<=n div2, опирается на элементы a[2*i] a[2*i+1] таким образом формируются тройки из элементов . такой тройкой являются элементы a[6] a[12] a[13], исходный массив может не удовлетворять этому свойству, поэтому его немного просеивают, т.е. с определенным условием. В процессе просеивания изменяется последовательность элементов в массиве. Начинается просеивание снизу. Половина элементов с ((ndiv2)+1) – го элемента по n-ый элемент являются элемент пирамиды, и их просеивать не надо. Но для всех элементов массива, двигаясь от конца к началу, проверяются тройки элементов, a[2*i] a[2*i+1]. В которых перемещают максимальный элемент на верх т.е. в a[i]. Для n-1 элементов, начиная с последнего, нужно осуществить следующие действия:

С начала нужно поменять местами очередной рабочий элемент с первым. Потом просеивается новый первый элемент так чтобы не затрагивалось уже отсортированное основание. Т.е. элементы с I по n. Первым рабочим элементом является n n-1 n-2 и т.д.

Вовторой части алгоритма должно осуществлятся n-1 перестановок. При первой перестановке самый верхний элемент становится последним элементом и становится первым в основании. После второй перестановке другой верхний элемент перемещается на место предпоследнего элемента массива и также входит в отсортированное основание. Процесс повторяется до тех пор пока в неотсортированной не останется один самый маленький элемент. Такой способ просеивания помогает выталкнуть на вершину пирамиды самый большой элемент а потом переместить его в начало отсортированной последовательности, т.е. в ее отсортированное основание.

Пример: необходимо отсортировать массив: 13, 0,29,56,7,15,78

Первое и второе просеивание:

13
0		29
56	7		15	78

13
56		78
0	7		15	29

78
56		13
0	7		15	29