QuickSort

rekurzivní třídění

 

QuickSort je znatelně nejrychlejší ze zde zmíněných algoritmů. Princip QuickSortu je velmi jednoduchý- pouze rozdělí čísla na menší a větší. Při opětovném zavolání se rozdělí menší zase na menší-menší a menší-větší a toto se provede i u větších (rozdělí se na větší-menší a větší-menší). Pří dalším zavolání se zase rozdělí každá část na menší a větší, až zbude v každé části pouze jedno číslo, nebo bude daná část uspo řádaná.

3 5 2 1 4 10 8 6 9 7
3 4 2 1 5 10 8 6 9 7
3 4 2 1   5 10 8 6 9 7
3 1 2   4   5 7 6   8 9 10
1   3 2   4   5 6   7   8 9 10
1   2   3   4   5 6   7   8 9 10

 

Neaktivní čísla

Střed pole

Prohozená čísla

1/2 část původního pole

 

Takto vypadá QuickSort v Delphi

QuickSort(p,0,length(p));

 

procedure QuickSort(var p:TPole;Zac,Kon:integer); //Uspořádá pole v rozsahu indexů od Zac do Kon

var i,j, {posouvané indexy} x, {dělící prvek} pom {pomocná proměnná pro výměnu} :integer;

begin

i:=Zac;
j:=Kon;
x:=(p[Zac]+p[Kon]) div 2; //Za x vezmeme třeba prvek ze středu pole

repeat

while p[i]<x do i:=i+1;
while p[j]>x do j:=j-1;

if i<j then // vyměnit prvky s indexy i a j
begin
pom:=p[i];p[i]:=p[j];p[j]:=pom;
pis(p);
i:=i+1;j:=j-1; //posun indexů na další prvky
end

else
if i=j then //indexy i a j se sešly a ukazují na x

begin
i:=i+1; //posun indexů je nezbytný
j:=j-1; //pro správné ukonční cyklu
end;

until i>j;

//úsek <Zac,Kon> je rozdělen na úseky <Zac,j> a <i,Kon>,
//které zpracujeme rekurzivním voláním procedury Quicksort:

if Zac<j then QSort(p,Zac,j);
if i<Kon then QSort(p,i,Kon);
end;