Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
Вычисляется индекс опорного элемента m.
Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.
Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
procedure QuickSortHore(var A: TArrayInt; L, R: integer);
var i, j: integer;
x, t: integer;
begin
while L < R do begin
x:= A[L];
i:= L; j:= R;
repeat
while A[i] < x do inc(i);
while x < A[j] do dec(j);
if i <= j then begin
t:= A[i]; A[i]:= A[j]; A[j]:= t;
inc(i); dec(j);
end;
until i > j;
if (j - L) > (R - i) then
begin
QuickSortHore(A, i, R);
R:= j;
end
else
begin
QuickSortHore(A, L, j);
L:= i;
end;
end;
end;
пример для Delphi / Pascal
Блок схема
Скорость работы
при массиве 15
QuickSort 1,6482
Пузырьковая сортировка 5,4787
при массиве 150
QuickSort 2,0699
Пузырьковая сортировка 184,2264
Метод сортировки Хора для строк пример для Delpi
type
TArrayString=array of string;
procedure QuickSortHoreString(var A: TArrayString; L, R: integer);
var i, j: integer;
x, t: string;
begin
while L < R do begin
x:= A[L];
i:= L; j:= R;
repeat
while A[i] < x do inc(i);
while x < A[j] do dec(j);
if i <= j then begin
t:= A[i]; A[i]:= A[j]; A[j]:= t;
inc(i); dec(j);
end;
until i > j;
if (j - L) > (R - i) then
begin
QuickSortHoreString(A, i, R);
R:= j;
end
else
begin
QuickSortHoreString(A, L, j);
L:= i;
end;
end;
end;
|
