Penjelasan Quick Sort

Penjelasan Quick Sort

Fungsi kedua adalah fungsi quicksort itu sendiri adalah :

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.

4.      Fungsi terakhir yang tidak wajib adalah yang memanggil basis rekursi.

Penjelasan Contoh Quick Sort

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.

Skrip Program

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);

        }

    }

Tweet