Pengurutan dengan Quicksort

Selamat malam semua, saya akan berbagi sedikit ilmu tentang pengurutan. Semoga bermanfaat ya. ^^

          Pengurutan elemen array baik secara menurun (descending) maupun menaik (ascending). Terdapat beberapa metode dalam pengurutan elemen array seperti quicksort, bubble sort, select sort, insert sort dan sebagainya. Kali ini saya akan mencoba jelaskan tentang Quicksort dalam mengatasi masalah pengurutan elemen array.

Quicksort

        Quicksort dapat diartikan pengurutan secara cepat. Mengapa disebut secara cepat ? karena pada pengurutan quicksort elemen array akan dibagi menjadi dua bagian dan dilakukan pengurutan pada kedua bagian, bagian yang belum terurut dibagi lagi menjadi dua bagian dan lakukan hingga tidak dapat dibagi lagi. Kegiatan tersebutlah yang sering kita sebut dengan cara rekursif. Rekursif yaitu pengulangan yang menggunakan dirinya sendiri. Agar lebih jelas lihat contoh berikut ini.

*******************************************************************************
#include<stdio.h>

void swap(int *a,int *b);
void quicksort(int x[],int left,int right);
void print(int x[],int n);

int main()
{
    int x[10]={15,12,4,21,3,5,15,22,1,2};
    quicksort(x,0,9);
    print(x,10);

    return 0;
}

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

}
void quicksort(int x[],int left,int right)
{
    int i,j,m;
    int pivot;

    i=left;
    j=right;
    m=(i+j)/2;
    pivot=x[m];

    while(i<=j)
    {
        if(x[i]<pivot)
        {
            i++;
        }
        else if(x[j]>pivot)
        {
            j--;
        }
        else{
        swap(&x[i],&x[j]);
        i++;
        j--;
        }
    }

    if(left<j){
        quicksort(x,left,j);
    }
    if(i<right){
        quicksort(x,i,right);
    }
}
void print(int x[],int n){
    int i;
    for(i=0;i<n ;i++)
    {
        printf(" %d",x[i]);
    }
    printf("\n");
}

          Diatas contoh source code menggunakan bahasa C tentang quicksort. Pada algoritma diatas dapat dilihat terdapat 3 prosedur yaitu prosedur penukaran (swap), quicksort, serta prosedur cetak(print). Pada inti program/ main terdapat Array x bertipe integer dengan jumlah 10 elemen yang isinya tidak terurut. Karena tidak terurut dipanggil prosedur Quicksort dengan tiga parameter yaitu array x, indeks elemen pertama x ( x[0] ) dan indeks terakhir array x ( x[n-1] ). 

          Pada prosedur quicksort cari indeks tengah dari array x, dengan memisalkan indeks awal sebagai i dan indeks terakhir sebagai j. Lakukan pengulangan selagi indeks awal <= indeks akhir. Jika isi indeks awal kurang dari isi dari indeks tengah maka indeks awal tadi bertambah 1. Jika indeks akhir lebih besar dari indeks tengah maka indeks akhir dikurang 1. Atau jika pernyataan diatas tidak terpenuhi maka lakukan penukaran elemen indeks tersebut. 

Karena array x masih belum terurut maka lakukan secara rekursif dengan aturan :

Jika indeks awal kurang dari indeks akhir (tak tetap) makan panggil prosedur Quicksort (array x, indeks awal, indeks akhir).

Jika indeks awal (tak tetap) kurang dari indeks akhir maka panggil prosedur Quicksort (array x, indeks awal, indeks akhir).  

          Jika pengurutan telah selesai, cetak dengan prosedur cetak yang memiliki parameter inputan array x dan jumlah elemen array. Lakukan perulangan untuk mencetaknya.