57.Метод быстрой сортировки(Хоара).

Сортировка методом Хоора (или быстрая сортировка) —это наиболее эффективный алгоритм внутренней сортировки. Его производительность зависит от выбора точки разбиения. При быстрой сортировке используется следующая стратегия:

1.Массив разбивается на меньшие подмассивы.

2.Подмассивы сортируются.

3.Отсортированные подмассивы объединяются.

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

Рассмотрим один из вариантов реализации сортировки Хоора.

Пример 15.6

В самой процедуре сортировки сначала выберем средний элемент. Потом, используя переменные i и j, пройдемся по массиву, отыскивая в левой части элементы больше среднего, а в правой – меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше j. Тогда получаем два подмножества, ограниченные с краев индексами l и r, а в середине – j и i. Если эти подмножества существуют (то есть i<r и j>l), то выполним их сортировку.

void Quicksort(int a[], int n, int left, int right)

{ int i=left, j=right; /*Инициализируем переменные левой и

правой границами подмассива*/

int test=a[(left+right)/2]; /*Выбираем в качестве

элемента разбиения средний элемент массива*/

do { while (a[i] < test)

i++;

/*находим элемент, больший элемента разбиения */

while (a[j] > test)

j--;

/*находим элемент, меньший элемента разбиения */

if (i<=j)

{ Swap(&a[i], &a[j);

i++; j--; }

}

while(i <= j); /*рекурсивно вызываем алгоритм для

правого и левого подмассива*/

if (i<right)

QuickSort(a, n, i, right);

if (j>left)

QuickSort(a, n, left, j);

}

Анализ быстрой сортировки

Быструю сортировку следует рассмотреть одной из первых при выборе метода внутренней сортировки. Алгоритм этой сортировки содержит сложную фазу разбиения и простую фазу слияния. В худшем случае выполненная работа эквивалентна работе при сортировке выбором. Производительность быстрой сортировки существенно зависит от выбора точки разбиения.