Главная » Pascal, Исходники, Сортировка » Алгоритм быстрой сортировки
Ноя
24

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

[sourcecode language=»css»]
program QuickSort1;
uses Crt;

const
n = 230; { количество элементов }
var
A: Array[1..n] of Integer;
k: Word;

procedure QSort(L, R: Integer); { рекурсивная процедура }
var
i, j, x, y: Integer;

begin
i:=L; j:=R; { инициализация индексов }
x:=A[(L+R) div 2]; { выбор элемента-барьера }

{ цикл разнонаправленных просмотров (левой и правой части массива) }
Repeat
While A[i] < x do Inc(i); { движение вправо }
While A[j] > x do Dec(j); { движение влево }
if i <= j then
begin
y:=A[i];
A[i]:=A[j];
A[j]:=y; { обмен }
Inc(i); Dec(j); { увеличение индексов }
end;
Until i > j;
if L < j then QSort(L, j); { рекурсивный вызов }
if i < R then QSort(i, R); { рекурсивный вызов }
end;

begin
ClrScr;
Randomize;
for k:=1 to n do
A[k]:=Random(25500)-10000; { инициализация }

QSort(1, n);
for k:=1 to n do
Write(A[k]:8); { вывод отсортированного массива }
Readln;
end.
[/sourcecode]

Выбираем наугад какой-либо элемент ( в нашем случае это X) и просматриваем слева наш массив до тех пор, пока не обнаружим элемент A[I] > X, затем будем просматривать массив справа, пока не встретим элемент A[j] < X.  Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть с элементами меньшими или равными X, а правую — с большими или равными X. Затем данный алгоритм точно также применяется к правой и левой части, т.е. начинается «деление частями частей», в программе это организовао рекурсивными вызовами процедуры QSort. Такой вот незамысловатый принцип действия алгоритма ;)




Данная сортировка является сильно усовершенствованой обменной сортировкой и считается найбыстрым методом сортировки массивов. Применяется к сортировке массивов с очень большим количеством элементов.



Понравилась статья? Сделай приятно ее автору, поделись с друзьями:


Хотите получать обновления данного блога на EMail?

Введите адрес Почтового Ящика:




Подтвердите подписку в письме пришедшем на Почту, после чего начнете получить рассылку.