Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Алгоритм быстрой сортировки

Классификационное название этого алгоритма — обменная сортировка сразделеннем .

Разработан Чарльзом Э. Р. Хоаром в 1962 г.
Один из лучших универсальных алгоритмов (одновременно не очень сложных), разработанных к настоящему времени. Отно- сится к группе алгоритмов обменной сортировки (как и пузырь- ковая сортировка).
Сортируемый массив разбивается на два подмассива, для чего сначала выбирается пограничное или опорное значение компаранд (т.е. значение, с которым будут сравниваться другие элементы массива). Все элементы, большие компаранда, перено- сятся в один подмассив, а меньшее — в другой. Весь процесс ліі- вторяется для каждого подмассива до тех пор, пока весь мас- сив не будет упорядочен.
Процесс сортировки носит рекурсивный характер.
184

Перенос в подмассивы может происходить следующим об-
разом:
Пусть имеются два индекса — i и у, причем сначала i = 0, у =
N — 1.
Сравниваются элементы k [i] и k[/], если обмен не требуется, то уменьшается на единицу и сравнения повторяются, с каж- дым шагом уменьшается на 1.
После первого обмена i увеличивается на единицу и сравне- ния повторяются с увеличением i на 1, пока не произойдет сле- дующий обмен, после которого опять начинает уменьшаться . И так до тех пор, пока i и не станут равны друг другу.
Представляет интерес вопрос о выборе компаранда. Суще-
ствуют варианты:

• 
  случайный выбор — иногда бывает наилучшим;
  

выборка небольшого числа элементов из подмассива и ис- пользовании в качестве компаранда медианы этой выборки. Ши- роко распространенным и эффективным является метод выборки трех элементов и взятие среднего из них;

• 
  один из экстремумов — наихудший вариант, хотя алго-
  

ритм работает и в этом случае;

• 
  элемент, находящийся в середине каждого из подмасси-
  

Процедура быстрой сортировки (метод Xoapa) на языке Паскаль с компарандом в середине каждого текущего подмасси-

procedure quicksort(item: array of char; left, right: integer);

var
i, ј: Integer; х, у: char;
begin
i left;
ј right;
х := item[int((left + right) / 2)]; repeat
while (item[i] < х) and (i < right) do i := i + 1;
while (х < item[j]) and (ј > left) do

185
-' J ^1;

if i <= j then
begin
y := item[i]; item[i] := item[j]; item[j] y;
i := i + 1; j := j - 1;
end;
until i < j;
if left < j then quick(item, left, j);
if i < right then quick(item, i, right);
end;

AHanorriuHas QyHKuHII HH RsI›IKIlX FH/FH+ .

void quick sort(char* item,int left,int right)

int i, j;

char comp, buf;
i = left; j = right;
comp = item[(left * right)/2]; // KOenapaHQ do {
while (item[i] < comp && i < right) i+*;
while (comp < item[j] && j > left)

if (i<=j)

buf = item[i]; // O/MeH item[i] = item[j]: item[j] = buf;

i+’;

BbI3OB
} while(i <= j); if (left < j)

quick sort(item, left, j); // PexypcxaHb H

186

if (i < right) quick_sort(item, i, right);
Изменение массива при сортировке по алгоритму Xoapa бу- дет иметь вид, показанный на рисунке 13.7 (компаранды под- чёркнуты, обрабатываемые подмассивы обведены).

f d а с b е

Рис. 13.7 — Обработка массива при быстрой сортировке

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