Сортировка Хоара

В настоящее время этот метод сортировки считается наилучшим. Он базируется на пузырьковом методе. В основе быстрой сортировки - принцип разбиения.

Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром. При программировании эффективно применение рекурсии.

Рассмотрим принцип работы алгоритма при упорядочении массива A из N элементов по возрастанию.

Значение какого-нибудь элемента, обычно центрального, записывается в переменную X. Просматриваются элементы массива. При движении слева-направо ищем элемент больше или равный X. А при движении справа-налево ищем элемент меньше или равный X. Найденные элементы меняются местами и продолжается встречный поиск.

После этого массив окажется разделенным на две части. В первой находятся элементы меньше либо равные X, а справа - больше либо равные X. Можно заменить исходную задачу о сортировке массива A на две подзадачи о сортировке полученных частей массива.

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

Замечание. Несмотря на всеобщую признательность быстрая сортировка обладает целым рядом недостатков. Ее эффективность проявляется не для всех массивов (например, если выбираемое центральное значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную).

Пример. Быстрая сортировка (Хоара) по возрастанию массива A из N целых чисел.

program Quick_Sort; 

var A:array[1..100] of integer; 
 N,i : integer; 
 {В процедуру передаются левая и правая границы сортируемого фрагмента} 
 
procedure QSort(L,R:integer); 
var X,y,i,j:integer; 
begin 
 X:=A[(L+R) div 2]; 
 i:=L; j:=R; 
 while i<=j do 
 begin 
 while A[i]X do j:=j-1; 
 if i<=j then 
 begin 
 y:=A[i]; A[i]:=A[j]; A[j]:=y; 
 i:=i+1; j:=j-1; 
 end; 
 end; 
 if L < j then QSort(L,j); 
 if i < R then QSort(i,R); 
end; 

begin 
 write('количество элементов массива '); 
 read(N); 
 for i:=1 to n do read(A[i]); 
 QSort(1,n); {упорядочить элементы с первого до n-го} 
 for i:=1 to n do write(A[i],' '); {упорядоченный массив} 
end.