Minggu, 26 Januari 2014
Quick Sort adalah algoritma sort yang tercepat dari antara sort-sort O(N log N) lainnya. Tetapi, Quick Sort juga algoritma yang running timenya tidak stabil. Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sangat cepat, tetapi pada kasus-kasus tertentu Quick Sort akan berjalan agak lambat, dan kalau sedang sial, untuk input tertentu (worst case) Quick Sort akan berjalan dengan waktu O(N2). Tapi pada umumnya (average case), Quick Sort berjalan dengan waktu O(N log N).
procedure
quicksort(terkiri,terkanan:longint);
var
kiri,kanan,temp,pivot:longint;
begin
if terkiri
begin
kiri:=terkiri;
kanan:=terkanan;
pivot:=data[(kiri+kanan) div 2];
while kiri<=kanan do
begin
while data[kiri]
while data[kanan]>pivot do dec(kanan);
if kiri<=kanan then
begin
temp:=data[kiri];
data[kiri]:=data[kanan];
data[kanan]:=temp;
inc(kiri);
dec(kanan);
end;
end;
quicksort(terkiri,kanan);
quicksort(kiri,terkanan);
end;
end;
