Tutorial C / C++ Metode Quick Sort

Algoritma Quick Sort dikembangkan pada tahun 1960 oleh C.A.R. Hoare ketika ia berada diUni Soviet sebagai mahasiswa tamu di Moscow State University, Ia mengembangkan algoritma itusebagai bagian dari mesin penerjemah, algoritma ini berfungsi mengurutkan kata-kata yang akan diterjemahkan supaya lebih mudah untuk dipasangkan dengan dengan kata-kata dari kamus yang sudah urut.Dalam algoritma Quick Sort dikenal apa yag disebut dengan pivot, pivot merupakan suatuelemen yang dipilh dari elemen array yang akan di urutkan, pivot dapat diambil dari elemen paling pinggir dari Array ataupun dari elemen yang tengah.

 
Dari ilustrasi diatas dapat dilihat bahwa pivotadalah elemen yang ditandai dengan warna merah, dalam pengoperasiannya elemen yang lebihbesar dari elemen pivot akan dipindah ke sebelah kanan pivot dann yang lebih kecil akan dipindah kesebelah kiri pivot, proses ini disebut dengan proses partitioning dan akan mengasilkan dua partisiarray, yaitu partisi yang lebih besar dari pivot dan partisi yang lebih kecil dari pivot. Proses diataskemudian dilakukan lagi pada masing-masing paritisi, sehingga mengasilkan partisi-partisi yang lain,seperti pada gambar di atas. 

secara ringkas, algoritma Quick Sort adalah sebagai berikut:

1. Pilih elemen pivot.
2. Pindahkan elemen array yang lebih kecil dari elemen pivot ke sebelah kiri pivot, danelemen yang lebih besar dari lemen pivot ke sebelah kanan pivot. 
3. Ulangi langkah 1 dan 2 untuk masing masing partisi yang terbentuk dari langkah 

untuk lebih jelasnya mari kita membuat satu program kecil dengan menggunakan metode Quick Sort, ketiklah listing dibawah ini:

#include <stdio.h>

#define MAX 11

#define MaxStack 11

int Data[MAX];

// Prosedur menukar data

void Tukar (int *a, int *b)

{

            int temp;

            temp = *a;

            *a = *b;

            *b = temp;

}

// Prosedur pengurutan metode Quick Sort

 void QuickSortNonRekursif()

{

            struct tump {

            int Kiri;

            int Kanan;

            }

            Tumpukan[MaxStack];

            int i, j, L, R, x, ujung = 1; Tumpukan[1].Kiri = 0;

            Tumpukan[1].Kanan = MAX-1;

            while (ujung!=0){

                        L = Tumpukan[ujung].Kiri;

                        R = Tumpukan[ujung].Kanan;

                        ujung--;

                        while(R > L){

                                    i = L;

                                    j = R;

                                    x = Data[(L+R)/2];

                                                while(i <= j){

                                                while(Data[i] < x)

                                                            i++;

                                                            while(x < Data[j])

                                                                        j--;

                                                                        if(i <= j){

                                                                        Tukar(&Data[i], &Data[j]);

                                                                        i++;

                                                                        j--;

                                                }

                        }

                        if(L < i){

                                    ujung++; Tumpukan[ujung].Kiri = i;

                                    Tumpukan[ujung].Kanan = R;

                        }

                        R = j;

            }

}

}

int main()

{

            int i;

            //Memasukkan data yang belum terurut

            printf("DATA SEBELUM TERURUT : \n");

            for(i=1; i<MAX; i++)

            {

                        printf("Data ke %d : ", i);

                        scanf ("%d", &Data[i]);

            }

            QuickSortNonRekursif();

           

            //Data setelah terurut

            printf("\nDATA SETELAH TERURUT");

            for(i=1; i<MAX; i++)

            {

                        printf("\nData ke %d : %d ", i, Data[i]);

            }

            //scanf("%d");

            return(0);

}

lebih kurang hasil dari program diatas adalah seperti pada gambar dibawah ini :











huhhhhh.. selesai sudah program kecil kita ini..
selamat berjuaang sobat.
semoga sobat semua menjadi programer2 kedepannya...
:)

Tweet