Структуры данных и алгоритмы

БЫСТРЫЕ СОРТИРОВКИ

• Быстрая обменная сортировка (сортировка Хоара).
• Быстрая сортировка вставкой (сортировка Шелла).
• Быстрые сортировки выбором.
• Сравнительный анализ методов сортировки.

4.10. Быстрая обменная сортировка (сортировка Хоара)

• Считается самой эффективной из известных внутренних сортировок.
• Получила название – Quicksort

Быстрая обменная сортировка (сортировка Хоара)

Идея алгоритма:

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

В примере реализации алгоритма создаётся процедура

В примере реализации алгоритма создаётся процедура

Hoor(left, right:integer) - в Pascal

или функция

void hoor(int left,right) – в C++

Алгоритм является рекурсивным.

Обозначения переменных:

right – правая граница рассматриваемой части массива A;

left – левая граница рассматриваемой части массива A;

x – разделитель.

При первом вызове процедуры полагается:

right = n; в C++ -> right = n-1;

left = 1; в C++ -> left = 0;

Сортировка Хоара (C/C++)

void hoor(int left, int right)

{

int i=left;

int j=right;

int x=a[(left+right)/2];

do {

while (a[i]<=x) i++;

//поиск с левой стороны элемента большего, чем разделитель

while (x

//поиск с правой стороны элемента меньшего, чем разделитель

if (i<=j) { меняем местами a[i] и a[j]; i++;j--; }

}

while (i<=j);

if (left

//применить процедуру сортировки для левой части массива

if (i

//применить процедуру сортировки для правой части массива

}

Среднее время выполнения алгоритма:

• Среднее время выполнения алгоритма:

T(n) = O(n × log n)

• Если массив почти упорядочен, время работы алгоритма может возрасти до квадратичного!
• Чтобы избежать этого, выбор разделителя производится методом медианы случайной выборки.
• Доказано, что наилучший обмен ключами достигается, когда разделитель разбивает массив по значениям «меньше разделителя» и «больше разделителя» примерно на равные части, т.е. разделитель близок к медиане.

Суть метода медианы случайной выборки:

Суть метода медианы случайной выборки:

• Из массива произвольно выбирается группа элементов (обычно до ста элементов), которые сортируются любым простым методом.
• Из середины отсортированной последовательности выбирается элемент, который далее используется в качестве разделителя.

Быстрая обменная сортировка (сортировка Хоара) - Пример

жүктеу/скачать 0.61 Mb.

Достарыңызбен бөлісу: