Definisi dan Cara Penggunaan Quick Sort

Quick Sort

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(N²). Tapi pada umumnya (average case), Quick Sort berjalan dengan waktu O(N log N). Algoritma ini sangat unik. Inti dari algoritma ini:

procedure Quicksort(a, b: integer);

var

    pivot: integer;

begin

    if (b > a) then

    begin

        pivot := A[(a + b) div 2];

        pindahkan semua elemen yang lebih kecil dari pivot ke sebelah kiri pivot

        pindahkan semua elemen yang lebih besar dari pivot ke sebelah kanan pivot

        misalkan pivot akhirnya berada di posisi j, maka

            Quicksort(a, j - 1);

            Quicksort(j + 1, b);

    end;

end;

dengan pemanggilan pertama

    Quicksort(1, N);

Basis dari prosedur rekursif ini adalah pada kasus b <= a, yaitu ketika hanya ada maksimum 1 elemen yang akan disort. Pivot dapat dipilih secara acak, dan bisa elemen apapun dari antara A[a..b]. Untuk kasus di atas, kita pilih elemen ke-(a + b) div 2.

Di bawah ini adalah ilustrasi Quick Sort, di mana elemen yang diberi kotak biru adalah pivot. Perhatikan bahwa elemen-elemen yang lebih kecil dari pivot diletakkan di sebelah kiri pivot, dan yang lebih besar di sebelah kanan pivot.

Salah satu implementasi Quick Sort dapat dilihat pada contoh berikut:

procedure Quicksort(a, b: integer);

var

    pivot: integer;

    left, right: integer;

begin

    if (b > a) then

    begin

        pivot := A[(a + b) div 2];

        left := a;  right := b;

        while (left <= right)

        begin

            while (A[left] < pivot)  left := left + 1;

            while (A[right] > pivot) right := right - 1;

            if (left <= right) then

            begin

                swap A[left] dengan A[right]

                left := left + 1;

                right := right - 1;

            end;

        end;

        // sampai di sini, tentu left > right

        Quicksort(a, right);

        Quicksort(left, b);

    end;

end;

Algoritma sort yang stabil

Kadang kala input yang kita miliki dapat memiliki elemen-elemen bernilai sama seperti

1 2 3 1 3 1 2 2

sehingga jika diurutkan dari kecil ke besar menjadi

1 1 1 2 2 2 3 3

Pada kasus ini tidak ada masalah, karena angka-angka yang sama tidak bisa dibedakan. Namun bagaimana jika Anda diberikan input

makan

lomba

main

tidur

toki

lalu Anda harus mengurutkan kata-kata tersebut dari yang pendek ke panjang? Bagaimana memecahkan kondisi seri (tie) antara "toki" dan "main", dan juga antara "makan", "lomba", dan "tidur"? Algoritma sort yang stabil (stable) adalah algoritma yang dapat mengurutkan input, dan jika menemukan kondisi seri, akan mengeluarkan elemen-elemen yang seri sesuai dengan urutan input awal. Pada contoh di atas, algoritma yang stabil akan mengeluarkan:

main

toki

makan

lomba

tidur

karena "main" muncul terlebih dahulu daripada "toki", dan "makan" muncul dahulu daripada "lomba", lalu daripada "tidur".

Dari algoritma-algoritma yang sudah kita pelajari di atas, semua algoritma stabil kecuali Quick Sort. Ketika menggunakan Quick Sort, kita tidak bisa menentukan urutan relatif dari elemen-elemen yang seri.

Berikut ini adalah tabel perbandingan algoritma-algoritma sort yang sudah kita pelajari:

Algoritma	Stabil	Running time	Catatan
Selection Sort	Ya	O(N2)	Running time tidak tergantung input
Insertion Sort	Ya	O(N2)	Jika input hampir terurut, running time menjadi sangat cepat
Bubble Sort	Ya	O(N2)	Lambat dibandingkan algoritma O(N2) lainnya
Merge Sort	Ya	O(N log N)	Running time tidak tergantung input
Quick Sort	Tidak	O(N log N)	Paling cepat dibandingkan algoritma O(N log N) lainnya, tetapi pada kasus terburuk (sangat jarang terjadi) menjadi O(N2). Algoritma ini adalah algoritma yang paling populer digunakan di kompetisi informatika.