Quicksort

Quicksort adalah algoritma sorting yang diciptakan oleh CAR Hoare. Kompleksitas algoritmanya adalah O(n log n).

Algoritma

Diberikan suatu list:

1. Pilih satu elemen yang kita sebut pivot. Elemen ini boleh acak, boleh elemen pertama, boleh elemen terakhir. Biasanya yang dipilih adalah elemen tengah.
2. Pindahkan semua elemen yang lebih kecil dari pivot ke sebelah kiri pivot, dan elemen yang lebih besar dari pivot ke sebelah kanan pivot (nilai yang sama dengan pivot boleh di kiri atau kanan). Sekarang pivot sudah berada di posisi yang benar. Langkah ini disebut langkah partisi.
3. Lakukan secara rekursif langkah 1 dan 2 terhadap list kiri (elemen-elemen yang lebih kecil dari pivot), dan terhadap list kanan (elemen-elemen yang lebih dari pivot).

Basis untuk rekursi adalah kasus list kosong.

Implementasi sederhana

Implementasi sederhana adalah implementasi yang memerlukan tambahan penyimpanan (untuk menyimpan list kiri dan kanan). Contohnya seperti ini dalam python:

       def quicksort(mylist):
           if (len(mylist)<=1):
               return mylist
           pivotposition = len(mylist)/2;
           pivot = mylist[pivotposition]
           del mylist[pivotposition]
           less = []
           greater = []
           for x in mylist:
               if (x<pivot):
                   less.append(x)
               else:
                   greater.append(x)
           sortedless = quicksort(less)
           sortedgreater = quicksort(greater)
           sortedless.append(pivot)
           return sortedless + sortedgreater

       print quicksort([20,1,4,3,2,9])

Implementasi naif dalam Lisp, kejelasan lebih dipentingkan (misalnya remove-if dan lambda expression bisa digunakan agar kita tidak perlu removeLE dan removeGT). Elemen pertama diambil sebagai pivot.

     (defun removeLE (x thelist)
        (if (null thelist)
            thelist
            (if (< (car thelist) x )
                (removeLE x (cdr thelist))
                (cons (car thelist) (removeLE x (cdr thelist)))
            )
       )
     )

     (defun removeGT (x thelist)
        (if (null thelist)
            thelist
            (if (>= (car thelist) x)            
                (removeGT x (cdr thelist))
                (cons (car thelist) (removeGT x (cdr thelist)))
            )
       )
     )

     (defun quicksort (mylist)
        (if (<= (length mylist) 1)
            mylist
            (let* ((pivot (car mylist))
               (therest (cdr mylist)))
               (append (removeGT pivot therest)
                   (cons pivot nil)
                   (removeLE pivot therest)               
               )
            )
        )
     )

Implementasi in-place sorting

Implementasi yang lebih rumit adalah tanpa menggunakan memori tambahan (in-place). Dalam pendekatan ini kita memerlukan fungsi pembantu agar algoritmnya lebih jelas:

Pertama kita perlu fungsi untuk mempartisi suatu list menjadi yang dikiri pivot dan dikanan pivot caranya. Sebelum melakukan partisi, kita tidak tahu di mana posisi akhir pivot (kecuali kita menghitung dulu jumlah elemen yang lebih kecil dari pivot). Kita bisa menghapus elemen pivot, dan menyimpannya di tempat lain sementara kita memproses elemen list selain pivot. Cara yang lebih mudah adalah kita pindahkan pivot ke posisi terakhir (tepatnya kita tukar pivot dengan elemen di posisi terakhir), lalu kita proses list dari elemen pertama sampai elemen sebelum terakhir (karena elemen terakhir adalah pivot). Dengan cara ini kita tidak perlu memori tambahan.

Pemrosesan dilakukan mulai elemen pertama sampai elemen sebelum elemen terakhir, jika nilainya kurang dari pivot, maka elemen ini seharusnya berada di kiri pivot. Meskipun kita belum tahu posisi akhir pivot ini nanti di mana, kita bisa meletakkan elemen pertama yang kita temui yang lebih kecil dari pivot di index pertama, elemen kedua yang lebih kecil dari pivot di index kedua, dan seterusnya. Jadi kita perlu variabel yang menunjukkan di posisi mana kita bisa meletakkan elemen yang lebih kecil dari pivot, sebut saja variabel ini p.

Di langkah terakhir, kita tahu posisi elemen-elemen yang kurang dari pivot, yaitu elemen-elemen yang ada sebelum posisi p. Di posisi p itulah di mana kita harus meletakkan pivot, jadi kita tukarkan elemen di posisi p dengan pivot. Fungsi perlu mengembalikan lokasi pivot yang baru, karena pivot sudah berpindah ketika diurutkan.

1. Tukar elemen pivot dengan elemen terakhir di list. Sekarang elemen pivot ada di paling kanan.
2. Set nilai p ke elemen pertama
3. Untuk setiap elemen e mulai dari pertama sampai elemen sebelum terakhir, bandingkan nilainya dengan pivot. Jika nilainya kurang dari pivot, tukarkan elemen e dengan elemen di posisi p, lalu tambahkan p dengan satu
4. Tukarkan elemen di posisi p dengan elemen terakhir (pivot).
5. Kembalikan lokasi pivot yang baru.

Saya akan menjelaskan algoritmanya menggunakan gambar. Pertama perhatikan bahwa kita bisa memecah list menjadi dua bagian, tidak peduli urutan di bagian kiri dan kanan. Jadi jika kita memiliki list:

Maka list tersebut bisa dipecah menjadi:

atau seperti ini:

Tergantung algoritma yang kita gunakan dalam memecah list. Saya contohkan dengan algoritma yang saya pilih ini. Saya memiliki list berikut 6, 4, 8, 5, 3, 1, 7, 2:

Saya pilih 5 sebagai pivot (sembarang elemen boleh menjadi pivot, saya pilih yang kira-kira di tengah). Tukarkan pivot ini dengan elemen terakhir.

Hasilnya seperti ini: 6*, 4, 8, 2, 3, 1, 7, 5 (pivot). Pada elemen pertama saya beri tanda bintang (*), akan saya jelaskan nanti gunanya.

Sekarang kita akan mulai memproses list dari elemen pertama sampai elemen sebelum pivot. Setiap kali menemukan elemen yang kurang dari pivot, saya pindahkan (kita tukar) dengan elemen yang diberi tanda bintang. Lalu bintang dipindahkan satu elemen ke kanan. Elemen pertama (6) lebih besar dari pivot (5), jadi kita cek elemen berikutnya yaitu 4. Karena 4 kurang dari pivot, kita tukarkan 4 dengan elemen yang bertanda *. Hasilnya:

Hasilnya: 4, *6, 8, 2, 3, 1, 7, 5 (pivot). Ingat bahwa setelah menukar, tanda * dipindah satu elemen ke kanan.

Berikutnya kita lihat bahwa 8 lebih dari pivot, jadi kita biarkan. Elemen 2 kurang dari pivot, sehingga perlu ditukar dengan *.

Dan hasilnya adalah: 4, 2, *8, 6, 3, 1, 7, 5 (pivot).

Elemen 3 juga kurang dari pivot, jadi kita perlu menukarnya.

Hasilnya adalah: 4, 2, 3, *6, 8, 1, 7, 5 (pivot).

Dan yang terakhir yang kurang dari pivot adalah 1.

Hasilnya adalah: 4, 2, 3, 1, *8, 6, 7, 5 (pivot).

Dan langkah terakhir adalah menukar posisi * dengan pivot:

Hasil akhirnya adalah list yang terbagi dua (semua elemen di kiri 5 lebih kecil dari 5 dan semua elemen di kanan 5 lebih besar dari 5): 4, 2, 3, 1, 5, 6, 7, 8:

Atau jika digambarkan, yang saya lakukan adalah seperti ini: memecah list awal, menjadi dua list, yang satu berisi elemen-elemen yang lebih kecil dari 5, dan list yang berisi elemen-elemen yang lebih besar atau sama dengan 5.

Implementasi

Pertama, kita asumsikan kita sudah memiliki fungsi untuk menukar nilai

     void swap(int *a, int *b)
     {
         int temp;
         temp = *a;
         *a = *b;
         *b = temp;
     }

Implementasi parition adalah seperti ini:

     int partition(int *elements, int left, int right, 
           int pivotposition)
     {
         int i;
         int pivotvalue = elements[pivotposition];
         int p = left;
         /*tukar pivot dengan elemen terakhir*/
         swap(&elements[pivotposition], &elements[right]);
         for (i=left; i<right; i++) {
             if (elements[i] < pivotvalue) {
                 swap(&elements[i], &elements[p]);
                 p++;
             }
         }
         /*letakkan pivot di posisi yang benar*/
         swap(&elements[p], &elements[right]);
         return p;
     }

]

Fungsi kedua adalah fungsi quicksort itu sendiri

1. Pilih sebuah elemen pivot
2. Panggil fungsi partisi, yang akan memindahkan semua elemen yang kurang dari pivot ke kiri, dan yang lebih dari pivot ke kanan. Kita akan mendapatkan lokasi pivot yang baru.
3. Secara rekursif panggil fungsi quicksort terhadap elemen-elemen di sebelah kiri dan sebelah kanan pivot.

     void _quicksort(int *elements, int left, int right)
     {  
         int pivotposition;
         /* jika left >= right, berarti list kosong */
         if (left < right) {
             pivotposition = left + (right - left) / 2;
             /* kita akan mendapatkan posisi pivot yang baru*/
             pivotposition = partition(elements, left, 
                                   right, pivotposition);
             /*urutkan elemen-elemen di kiri pivot*/
             _quicksort(elements, left, pivotposition - 1);
             /*urutkan elemen-elemen di kanan pivot*/
             _quicksort(elements, pivotposition + 1, right);
         }
     }

Fungsi terakhir yang tidak wajib adalah yang memanggil basis rekursi.

     void quicksort(int *elements, int len)
     {
         _quicksort(elements, 0, len - 1 );
     }

Ini bisa diuji dengan fungsi main seperti ini:

     int main(int argc, char *argv[])
     {
         int i;
         int mylist[] = {1, 8, 2, 0, 3, 4, 9, 5, 6, 7};
         quicksort(mylist, 10);
         for (i = 0; i< 10; i++) {
             printf("%d ", mylist[i]);
         }
         printf("\n");
         return 0;
     }

Pendekatan lain fungsi partisi

Ada pendekatan lain untuk fungsi partisi. Pertama kita sebenarnya bisa membiarkan fungsi partisi yang memilihkan pivot (tidak dari fungsi quicksort). Kedua adalah dalam proses partisi. Untuk mempartisi list menjadi dua bagian. Kita bisa menggunakan dua indeks yang bergerak dari kiri ke kanan, dan dari kanan ke kiri, dan menukar elemen yang posisinya salah.

Indeks pertama i bergerak dari awal list ke kanan, dan indeks kedua j bergerak dari kanan ke kiri. Jika nilai elemen di indeks i kurang dari pivot, tambahkan i dengan 1 (cek posisi berikutnya, karena posisinya sudah benar), jika nilai di indeks i lebih besar dari pivot, maka proses dihentikan. Kita jalankan indeks j untuk menemukan elemen yang lebih kecil yang bisa ditukarkan.

Indeks j bergerak dari kanan ke kiri mulai dari elemen terakhir menuju tengah, jika nilai elemen di posisi j lebih besar dari pivot, kurangkan j dengan 1. Jika nilai di posisi j kurang dari pivot, maka kita hentikan proses ini.

Jika elemen belum terurut, suatu saat i akan berhenti di suatu nilai yang lebih besar dari pivot, dan j berhenti di suatu nilai yang lebih kecil dari pivot. Ketika ini terjadi, tukarkan elemen di posisi i dengan elemen di posisi j. Berikutnya ulangi proses untuk menaikkan indeks i dan mengurangi indeks j, sampai i >= j.

1. Pilih pivot.
2. Set i ke posisi elemen pertama, dan j ke posisi elemen terakhir.
3. Selama elemen di posisi i kurang dari pivot, tambahkan i dengan 1.
4. Selama elemen di posisi j lebih dari pivot, kurangkan j dengan 1.
5. Jika i masih kurang dari j, tukar elemen di posisi i dengan elemen di posisi j
6. Ulangi langkah 2 sampai 5 hingga i >= j

Dalam C kodenya menjadi:

    int partition(int *elements, int left, int right)
    {
        int i, j;
        int pivotposition;
        int pivotvalue;

        pivotposition = left + (right-left)/2;
        pivotvalue = elements[pivotposition];

        i = left;
        j = right;

        do {
            while (elements[i] < pivotvalue)
                ++i;
            while (elements[j] > pivotvalue)
                --j;
            if (i<j) {
                swap(&elements[i], &elements[j]);           
            }

        } while (i<j);

        return j;
    }

Fungsi _quicksort hampir sama, hanya bagian menghasilkan pivot yang dihapus

    void _quicksort(int *elements, int left, int right)
    {   
        int pivotposition;
        /* jika left >= right, berarti list kosong */
        if (left < right) {
            pivotposition = partition(elements, left, right);
            /*urutkan elemen-elemen di kiri pivot*/
            _quicksort(elements, left, pivotposition - 1);
            /*urutkan elemen-elemen di kanan pivot*/
            _quicksort(elements, pivotposition + 1, right);
        }
    }

Last update: late Wednesday evening, March 27th, 2019

Copyright © 2009-2018 Yohanes Nugroho