Описание «быстрой» сортировки




Как и для большинства алгоритмов сортировки, методика «быстрой» сортировки взята из повседневного опыта. Чтобы отсортировать большую стопку алфавитных карточек по именам, можно разбить ее на две меньшие стопки относительно какой-нибудь буквы, например K. Все имена, меньшие или равные K, идут в одну стопку, а остальные – в другую.

Рис.2

Затем каждая стопка снова делится на две. Например, на рисунке 2 точками разбиения являются буквы F и R. Процесс разбиения на все меньшие и меньшие стопки продолжается.

В алгоритме «быстрой» сортировки применяется метод разбиения с определением центрального элемента. Так как мы не можем позволить себе удовольствие разбрасывать стопки по всему столу, как при сортировке алфавитных карточек, элементы разбиваются на группы внутри массива. Рассмотрим алгоритм «быстрой» сортировки на примере, а затем обсудим технические детали. Пусть дан массив, состоящий из 10 целых чисел:

A = 800, 150, 300, 600, 550, 650, 400, 350, 450, 700

Фаза сканирования

Массив имеет нижнюю границу, равную 0 (low), и верхнюю границу, равную 9 (high). Его середина приходится на 4 элемент (mid). Первым центральным элементом является A[mid] = 550. Таким образом, все элементы массива A разбиваются на два подсписка: Sl и Sh. Меньший из них (Sl) будет содержать элементы, меньшие или равные центральному. Подсписок Sh будет содержать элементы большие, чем центральный. Поскольку заранее известно, что центральный элемент в конечном итоге будет последним в подсписке Sl, мы временно передвигаем его в начало массива, меняя местами с A[0] (A[low]). Это позволяет сканировать подсписок A[1]--A[9] с помощью двух индексов: scanUp и scanDown. Начальное значение scanUp соответствует индексу 1 (low+1). Эта переменная адресует элементы подсписка Sl. Переменная scanDown адресует элементы подсписка Sh и имеет начальное значение 9 (high). Целью прохода является определение элементов для каждого подсписка.

Рис.3

Оригинальность «быстрой» сортировки заключается во взаимодействии двух индексов в процессе сканирования списка. Индекс scanUp перемещается вверх по списку, а scanDown – вниз. Мы продвигаем scanUp вперед и ищем элемент A[scanUp] больший, чем центральный. В этом месте сканирование останавливается, и мы готовимся переместить найденный элемент в верхний подсписок. Перед тем, как это перемещение произойдет, мы продвигаем индекс scanDown вниз по списку и находим элемент, меньший или равный центральному. Таким образом, у нас есть два элемента, которые находятся не в тех подсписках, и их можно менять местами.

Swap (A[scanUp], A[scanDown]); // менять местами партнеров

Этот процесс продолжается до тех пор, пока scanUp и scanDown не зайдут друг за друга (scanUp = 6, scanDown = 5). В этот момент scanDown оказывается в подсписке, элементы которого меньше или равны центральному. Мы попали в точку разбиения двух списков и указали окончательную позицию для центрального элемента. В нашем примере поменялись местами числа 600 и 450, 800 и 350, 650 и 400 (см. рисунок 4).

Рис.4

Затем происходит обмен значениями центрального элемента A[0] с A[scanDown]:

Swap(A[0], A[scanDown]);

В результате у нас появляются два подсписка A[0] – A[5] и A[6] – A[9], причем все элементы первого подсписка меньше элементов второго, и последний элемент первого подсписка является его наибольшим элементом. Таким образом, можно считать, что после проделанных операций подсписки разделены элементом А[5] = 550 (рисунок 5). Если теперь отсортировать каждый подсписок по отдельности, то у нас получится полностью отсортированный массив. Заметьте, что по сути оба этих подсписка являются такими же массивами, как и исходный, поэтому к ним можно применить тот же самый алгоритм. Применение того же алгоритма к частям массива называется рекурсивной фазой.

Рекурсивная фаза

Одним и тем же методом обрабатываются два подсписка: Sl(A[0] – A[4]) и Sh(A[6] – A[9]). Элемент А[5] обрабатывать не надо, так как он уже находится на своем месте.

Тот же алгоритм применяется для каждого подсписка, разбивая эти подсписки на меньшие части, пока в подсписке не останется одного элемента или пока подсписок не опустеет.

Рис.5

Алгоритм QuickSort

Этот рекурсивный алгоритм разделяет список A[low]--A[high] по центральному элементу, который выбирается из середины списка

mid = (high + low) / 2; pivot = A[mid];

После обмена местами центрального элемента с A[low], задаются начальные значения индексам scanUp = low + 1 и scanDown = high, указывающим на начало и конец списка, соответственно. Алгоритм управляет этими двумя индексами. Сначала scanUp продвигается вверх по списку, пока не превысит значение scanDown или пока не встретится элемент больший, чем центральный.

while (scanUp <= scanDown && A[scanUp] <= pivot) scanUp++;

После позиционирования scanUp индекс scanDown продвигается вниз по списку, пока не встретится элемент, меньший или равный центральному.

while (pivot < A[scanDown]) scanDown--;

По окончании этого цикла (и при условии что scanUp < scanDown) оба индекса адресуют два элемента, находящихся не в тех подсписках. Эти элементы меняются местами.

Swap(A[scanUp], A[scanDown]);

Обмен элементов прекращается, когда scanDown становится меньше, чем scanUp. В этот момент scanDown указывает начало левого подсписка, который содержит меньшие или равные центральному элементы. Индекс scanDown становится центральным. Взять центральный элемент из A[low]:

Swap(A[low], A[scanDown]);

Для обработки подсписков используется рекурсия. После обнаружения точки разбиения мы рекурсивно вызываем QuickSort с параметрами low, mid-1 и mid+1, high. Условие останова возникает, когда в подсписке остается менее двух элементов, так как одноэлементный или пустой массив упорядочивать не нужно.

// Swap меняет местами элементы массива. Соответствующий тип данных // должен поддерживать операцию «=». template <class T> void Swap(T & el1, T & el2) { T tmp = el1; el1 = el2; el2 = tmp; }   // QuickSort принимает в качестве параметров массив // и предельные значения его индексов template <class T> void QuickSort(T A[], int low, int high) { // локальные переменные, содержащие индекс середины - mid, // центральный элемент и индексы сканирования T pivot; int scanUp, scanDown; int mid;   // если диапазон индексов не включает в себя // как минимум два элемента, завершить работу if(high - low <= 0) return; else if(high - low == 1) { // если в подсписке два элемента, сравнить их между собой // и поменять местами при необходимости if(A[high] < A[low]) Swap(A[low], A[high]); return; }   // Рассчитать индекс середины и поместить значение соответствующего // элемента массива в переменную pivot. mid = (low + high)/2; pivot = A[mid];   // Поменять местами центральный и начальный элементы списка. Swap(A[mid], A[low]); // Инициализировать индексы scanUp и scanDown. scanUp = low + 1; scanDown = high;   // Искать элементы, расположенные не в тех подсписках. // Остановиться при scanDown < scanUp. do { // Продвигаться вверх по первому подсписку. Остановиться, // когда scanUp укажет на второй подсписок или если // указываемый этим индексом элемент > центрального. while(scanUp <= scanDown && A[scanUp] <= pivot) scanUp++;   // Продвигаться вниз по второму подсписку. Остановиться, // когда scanDown указжет на элемент >= центральному. while(A[scanDown] > pivot) scanDown--;   // Если индексы все еще в своих подсписках, то они указывают // на два элемента, находящихся не в тех подсписках. if(scanUp < scanDown) { // Поменять их местами Swap(A[scanUp], A[scanDown]); } } while(scanUp < scanDown);   // Скопировать элемент на который указывает точка разбиения // в первый элемент первого подсписка,... A[low] = A[scanDown]; // а центральный элемент в точку разбиения A[scanDown] = pivot;   // если первый подсписок (low...scanDown-1) имеет 2 или более // элемента, выполнить для него рекурсивный вызов QuickSort if(low < scanDown-1) QuickSort(A, low, scanDown-1);   // если второй подсписок (scanDown+1...high) имеет 2 или более // элемента, выполнить для него рекурсивный вызов QuickSort if(scanDown+1 < high) QuickSort(A, scanDown+1, high); }


Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-08-04 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: