Algoritma Quicksort pada Pascal

Quicksort adalah salah satu algoritma untuk mengurutkan sejumlah deret baris bilangan. Umumnya quicksort memiliki kompleksitas O(n log n) atau setara dengan mengurutkan n bilangan. Namun di saat worst case-nya, kompleksitasnya menjadi O(n^2), namun itu jarang terjadi. Dan ketika best case-nya,quicksort memiliki kompleksitas O(log n). Jadi, kompleksitas dari quicksort dapat berubah-ubah, tergantung dengan baris bilangan/data yang ingin diurutkan.

Quicksort bukanlah algoritma yang tercepat dan terbaik dalam pengurutan, tapi setidaknya jauh lebih baik dari beberapa algortima lain seperti bubblesort,insertion sort,dll.

Algoritma ini sangat berguna ketika kita ingin mengurutkan data yang lumayan besar. Dalam dunia olimpiade komputer, quicksort adalah salah satu algoritma yang penting dan sering digunakan ketika sedang coding(membuat program) yang membutuhkan pengurutan data-data yang besar di dalamnya.

Berikut adalah contoh dari potongan program pascal untuk quicksort:

procedure quicksort(a,b:longint);

var ki,ka,mid,temp:longint;

begin

ki:=a; ka:=b; mid:=arr[(a+b) div 2]; {arr adalah variabel untuk array}

while ki<=ka do begin

    while arr[ki]<mid do inc(ki);             {*baris ke-6}

    while arr[ka]>mid do dec(ka);          {*baris ke-7}

    if ki<=ka do begin

        {3 baris berikut merupakan perintah untuk menukarkan isi 2 array}

        temp:=arr[ki];

        arr[ki]:=arr[ka];

        arr[ka]:=temp;

        inc(ki); dec(ka);

    end;

end;

if a<ka then quicksort(a,ka);

if ki<b then quicksort(ki,b);

end;

Potongan algoritma di atas akan mengurutkan data array dari ukuran terkecil hingga yang terbesar. Algoritma di atas cuma salah satu bentuk algoritma quicksort yang sering saya pakai. Jadi kalian bisa membuat algortima quicksort dengan bentuk yang lain.

Kalian juga bisa mengganti variabelnya, tak harus sesuai dengan contoh yang di atas.

Selamat Mencoba.

note:

a dan b adalah jangkauan data array yang ingin kita urutkan. bila kalian ingin mengurutkan data sebaliknya (besar ke kecil), kalian tinggal mengubah tanda '<' atau '>' menjadi kebalikannya di baris 6 dan 7.