Sorting

1.    Pengertian Sorting

Sorting merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:

a.    Urut naik (ascending) Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar.

b.    Urut turun (descending) Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Ada 2 metode sorting data yang akan dubahas dalam tulisan kali ini yaitu, bubble sort dan quick sort.

2.    Bubble Sort

Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti “gelembung air” untuk elemen struktur data yang semestinya berada pada posisi awal. Cara kerjanya adalah dengan berulang-ulang melakukan proses looping terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam proses looping tersebut,nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap). Algoritma sorting ini disebut juga dengan comparison sort dikarenakan hanya mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.

Algoritma bubble sort dapat diringkas sebagai berikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:

a.    Lakukan looping untuk membandingkan dua elemen berdekatan. Looping ini dilakukan dari belakang.

b.    Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses looping berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan.

c.     Ulangi langkah di atas untuk struktur data yang tersisa.

Contoh Program Bubble Sort

#include<iostream>

#include<conio.h>

using namespace std;

int main()

{

    int i, j, pil, n, sementara;

    cout<<"Masukkan banyak data acak : "; cin>>n;

    int data[n];

    for(i=0;i<n;i++)

    {

        cout<<"Data ke-"<<i+1<<" : "; cin>>data[i];

    }pilihan :

    cout<<"Data : ";

    for(i=0;i<n;i++){cout<<data[i]<<", ";}

    cout<<endl<<"====================================="<<endl;

    cout<<"Sorting bubble : "<<endl;

    cout<<"1. Ascending "<<endl;

    cout<<"2. Descending "<<endl;

    cout<<"Masukkan pilihan menu (1/2) : ";cin>>pil;

    switch(pil)

    {

    case 1:

        for(i=0; i<=n-2; i++)

        {

            for(j=n-1; j>=i+1; j--)

            {

                if(data[j]<data[j-1])

                {

                    sementara=data[j];

                    data[j]=data[j-1];

                    data[j-1]=sementara;

                }

            }

        }

        cout<<"Data setelah disorting : ";

        for(i=0; i<n; i++)

        {

            cout<<data[i]<<", ";

        }

        break;

    case 2:

        for(i=0; i<=n-2; i++)

        {

            for(j=n-1; j>=i+1; j--)

            {

                if(data[j]>data[j-1])

                {

                    sementara=data[j];

                    data[j]=data[j-1];

                    data[j-1]=sementara;

                }

            }

        }

        cout<<"Data setelah disorting : ";

        for(i=0; i<n; i++)

        {

            cout<<data[i]<<", ";

        }

        break;

    default:

        cout<<"Anda salah memasukkan kode "<<endl;

        goto pilihan;

        break;

    }

    getche();

    return 0;

}

Hasil Running

3.    Quick Sort

Dalam algoritma Quick Sort dikenal apa yag disebut dengan pivot, pivot merupakan suatu elemen yang dipilh dari elemen array yang akan di urutkan, pivot dapat diambil dari elemen paling pinggir dari Array ataupun dari elemen yang tengah.

Dalam pengoperasiannya elemen yang lebih besar 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 partisi array, yaitu partisi yang lebih besar dari pivot dan partisi yang lebih kecil dari pivot. Proses diatas kemudian dilakukan lagi pada masing-masing paritisi,

Secara ringkas, algoritma Quick Sort adalah sebagai berikut:

a.       Pilih elemen pivot.

b.      Pindahkan elemen array yang lebih kecil dari elemen pivot ke sebelah kiri pivot, dan elemen yang lebih besar dari lemen pivot ke sebelah kanan pivot.

c.       Ulangi langkah 1 dan 2 untuk masing masing partisi yang terbentuk dari langkah.

Contoh Program Bubble Sort

#include <iostream>

#define n 20

using namespace std;

int Ar[n];

void

quickSort(int arr[], int left, int right);

int main()

{

    int jumlahBil=5;

    cout<<"Masukkan jumlah bilangan dalam : ";

    cin>>jumlahBil;

    int Ar[jumlahBil];

    for(int i=0; i<jumlahBil;i++)

    {

        cout<<"Bilangan ke-"<< i+1 << " : ";

        cin>>Ar[i];

    }

    quickSort(Ar,0,jumlahBil-1 );

    cout<<"Data yang telah diurutkan"<<endl;

    for(int i=0; i<jumlahBil;i++)

    {

        cout<<Ar[i]<<"\n";

    }

    cin.get();

    return 0;

}

void quickSort(int arr[], int left, int right)

{

    int i = left, j = right;

    int tmp;

    int pivot = arr[(left + right) / 2];

    while (i <= j)

    {

        while (arr[i] < pivot)

        i++;

        while (arr[j] > pivot)

        j--;

        if (i <= j)

        {

            tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

            i++;

            j--;

        }

    };

    if (left < j)

    quickSort(arr, left, j);

    if (i < right)

    quickSort(arr, i, right);

}

Hasil Running

 


Sumber :
Modul Praktikum Alpro2 Politeknik Negeri Tanah Laut 2018