Sorting C++

Pengurutan (Sorting)

           Pengurutan (sorting) adalah proses mengatur sekumpulan obyek menurut urutan atau susunan tertentu. Urutan tersebut dapat menaik (ascending) atau menurun (descending). Jika diberikan n buah elemen disimpan di dalam array L, maka :

• Pengurutan menaik adalah L[0] < L[2] < ... < L[n-1]
• Pengurutan menurun adalah L[0] > L[2] > ... > L[n-1]
• 
  

1. Pengurutan Internal, yaitu pengurutan terhadap sekumpulan data disimpan di dalam memori utama komputer.
2. Pengurutan Eksternal, yaitu pengurutan data yang disimpan di dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu dimuat semuanya dalam memori computer, disebut juga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.

          Karena pengaksesan memori utama lebih cepat daripada memori sekunder, maka pengurutan internal lebih cepat daripada pengurutan eksternal. Bermacam-macam metode yang dipakai untuk melakukan pengurutan, antara lain :

• Bubble Sort
• Selection Sort
• Insertion Sort
• Heap Sort
• Shell Sort
• Quick Sort
• Merge Sort
• Radix Sort
• Tree Sort

Kali ini saya hanya akan membahas bentuk sorting yang mendasar beserta codingannya yaitu Bubble Sort dan Selection Sort.

Metode Pengurutan Gelembung (Bubble Sort)

Metode ini diinspirasi oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun lebih ringan dibandingkan dengan berat jenis air, sehingga gelembung sabun selalu terapung di permukaan air. Prinsip pengapungan inilah yang diterapkan ke metode ini, dimana nilai yang paling rendah berada di posisi paling atas, melalui proses pertukaran.

Konsep dasar dari metode ini adalah setiap data yang ada di kumpulan, dibandingkan dengan data-data lainnya, artinya jika jumlah data sebanyak 5, maka akan terjadi perbandingan sebanyak (5-1)² = 16 kali.

Untuk satu data, akan dibandingkan sebanyak 4 kali terhadap data yang lainnya.

Atau secara umum dapat ditarik rumus, untuk jumlah data sebanyak n buah, maka :

Jumlah iterasi perbandingannya = (n-1)² 

Jika data-data tersebut disimpan di dalam array L, maka :

1. Untuk pengurutan menaik, pembandingnya sebagai berikut : L[n] < L[n-1]
2. Untuk pengurutan menurun, perbandingannya sebagai berikut : L[n] > L[n-1]

Jika kondisi diatas terpenuhi, maka nilai data yang ada di indeks n-1 akan ditukar dengan nilai data yang ada di indeks n.

Perhatikan program pengurutan menaik di bawah ini :

#include <iostream>

using namespace std;

void tampilkan_larik(int data[],int n)

{

int i;

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

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

cout<<endl;

}

void bubble_sort(int data[],int n)

{

int tahap,j,tmp;

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

{

for(j=0 ; j< n-tahap; j++)

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

{

//tukarkan

tmp       = data [j];

data[j]   = data[j+1];

data[j+1] = tmp;

}

cout<<"Hasil Tahap "<<tahap<<":" ;

tampilkan_larik(data,n);

}

}

int main()

{

int const JUM_DATA =8;

int i;

int data[]= {25,57,48,37,12,91,80,33};

bubble_sort(data, JUM_DATA);

//hasil pengurutan

cout<<endl;

cout<<"________________"<<endl;

cout<<"HASIL PENGURUTAN"<<endl;

cout<<"________________"<<endl;

tampilkan_larik(data, JUM_DATA);

return 0;

}

Dan hasilnya adalah

                  

            Cara diatas adalah pengurutan dengan menggunakan Bubble Sort yaitu metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut.

Metode Pengurutan Pilih (Selection Sort)

Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data array L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikut sertakan pada proses pencarian data maksimum/minimum berikutnya. Perhatikan ilustrasi berikut :

Misalkan ada sekumpulan data acak berjumlah n elemen yang disimpan di dalam array L, akan diurut menaik, maka langkah-langkah yang harus dilakukan adalah : 

1. Menentukan jumlah iterasi, yaitu pass = n-
2. Untuk setiap pass ke-l = 0,1,2, ..., pass, lakukan

• Cari elemen terbesar (maks) dari elemen ke-i sdampai ke-(n-1)
• Pertukaran maks dengan elemen ke-i
• Kurangkan n satu (n=n-1)

Contoh program :

#include <iostream>

using namespace std;

void tampilkan_larik(int data[],int n)

{

int i;

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

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

cout<<endl;

}

void selection_sort(int data[],int n)

{

int posmin,posawal,j,tmp;

for(posawal=0; posawal<n-1; posawal++)

{

posmin = posawal;

for(j=posawal+1 ; j< n; j++)

if (data[posmin] >data[j])

posmin =j;

{

//tukarkan

tmp       = data [posawal];

data[posawal]   = data[posmin];

data[posmin] = tmp;

}

cout<<"Hasil Tahap "<<posawal<<":" ;

tampilkan_larik(data,n);

}

}

int main()

{

int const JUM_DATA =8;

int i;

int data[]= {25,57,48,37,12,91,80,33};

selection_sort(data, JUM_DATA);

//hasil pengurutan

cout<<endl;

cout<<"________________"<<endl;

cout<<"HASIL PENGURUTAN"<<endl;

cout<<"________________"<<endl;

tampilkan_larik(data, JUM_DATA);

return 0;

}

Hasil dari coding diatas adalah

          Cara diatas adalah metode pengurutan dengan menggunakan Selection Sort yaitu Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang 

maka dicatat posisinya dan kemudian ditukar. Secara garis besar, metode ini relatif lebih cepat dibandingkan dengan metode gelembung, karena pertukaran hanya sekali dilakukan pada setiap pass, sehingga waktu pengurutan dapat dikurangi.

          Setelah kita mencoba melakukan pengurutan dengan metode menaik (ascending) sekarang kita akan mencoba dengan metode menurun (descending).

 Bubble Sort Descending

#include <iostream>

using namespace std;

void tampilkan_larik(int data[],int n)

{

int i;

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

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

cout<<endl;

}

void bubble_sort(int data[],int n)

{

int tahap,j,tmp;

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

{

for(j=0 ; j< n-tahap; j++)

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

{

//tukarkan

tmp       = data [j];

data[j]   = data[j+1];

data[j+1] = tmp;

}

cout<<"Hasil Tahap "<<tahap<<":" ;

tampilkan_larik(data,n);

}

}

int main()

{

int const JUM_DATA =8;

int i;

int data[]= {25,57,48,37,12,91,80,33};

bubble_sort(data, JUM_DATA);

//hasil pengurutan

cout<<endl;

cout<<"________________"<<endl;

cout<<"HASIL PENGURUTAN"<<endl;

cout<<"________________"<<endl;

tampilkan_larik(data, JUM_DATA);

return 0;

}

Selection Sort Descending

#include <iostream> using namespace std; void tampilkan_larik(int data[],int n) {     int i;     for (i=0 ; i<n; i++)         cout<< data[i] <<" ";     cout<<endl; } void selection_sort(int data[],int n) {     int posmin,posawal,j,tmp;     for(posawal=0; posawal<n-1; posawal++)     {         posmin = posawal;         for(j=posawal+1 ; j< n; j++)             if (data[posmin] <data[j])                 posmin =j;         {             //tukarkan             tmp       = data [posawal];             data[posawal]   = data[posmin];             data[posmin] = tmp;         }         cout<<"Hasil Tahap "<<posawal<<":" ;         tampilkan_larik(data,n);     } } int main() {     int const JUM_DATA =8;     int i;     int data[]= {25,57,48,37,12,91,80,33};     selection_sort(data, JUM_DATA);     //hasil pengurutan     cout<<endl;     cout<<"________________"<<endl;     cout<<"HASIL PENGURUTAN"<<endl;     cout<<"________________"<<endl;     tampilkan_larik(data, JUM_DATA);     return 0; }