Sorting

Kali ini saya akan membahas mengenai pengurutan, atau istilah kerennya sorting. Pengurutan atau sorting dapat diartikan sebagai proses penyusunan kembali sekumpulan objek ke dalam urutan tertentu. Adapun tujuan dari pengurutan atau sorting ini adalah untuk memudahkan dalam pencarian anggota suatu himpunan. Selain itu dapat memepercepat untuk mengetahui data terbesar dan data terkecil. Adapun proses yang terjadi dalam pengurutan adalah perbandingan data dan pertukaran data.
Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:
1. urut naik (ascending)
Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar
2. urut turun (descending)
Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Terdapat bermacam-macam metode sorting, diantaranya adalah

1.  Insertion Sort (Metode Penyisipan)
2.  Selection Sort (Metode Seleksi)
3.  Bubble sort(Metode Gelembung)
4.  Shell Sort (Metode Shell)
5.  Quick Sort (Metode Quick)
6.  Merge Sort (Metode Penggabungan)

Dari metode-metode tersebut yang manakah yang terbaik? Tidak ada metode atau algoritma terbaik untuk setiap situasi yang kita hadapi, bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan.
Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain:
•    banyak data yang diurutkan
•    kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki
•    tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan yang lain.
Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan.

Berikut akan dijelaskan 2 metode sorting yang paling sering digunakan, yaitu selection sort dan insertion sort disertai dengan contoh program dalam bahasa C++.

1. Selection Sort
Selection Sort atau metode seleksi ialah melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut :

1. Mencari data terkecil dari data pertama sampai dengan data terakhir, kemudian ditukar dengan data pertama.
2. Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian ditukar posisinya dengan data kedua.
3. Mencari data terkecil dari data ketiga sampai dengan data terakhir, kemudian ditukar posisinya dengan data ketiga.
4. Begitu seterusnya sampai semua data terurut. Apabila terdapat n buah data yang akan diurutkan, maka akan membutuhkan (n-1) langkah pengurutan, dimana data terakhir, yaitu data ke-n tidak perlu diurutkan karena hanya tinggal satu-satunya.

Berikut prosedur dari selection sort:

void SelectionSort(){
 int i, j, k;
 for(i=0; i Data[j])
  k = j;
  Tukar(&Data[i], &Data[k]);
 }
}

2. Insertion Sort
Proses yang terjadi pada pengurutan dengan menggunakan metode Insertion sort atau metode penyisipan adalah dimulai dari data ke-2, kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama diandaikan memang sudah pada tempatnya.
Berikut ini adalah prosedur yang menggunakan metode penyisipan:

void StraighInsertSort()
{
 int i, j, x;
 for(i=1; i {
  x = Data[i];
  j = i - 1;
  while (x < Data[j])
  {
   Data[j+1] = Data[j];
   j--;
  } 
  Data[j+1] = x;
 }  
}

Contoh Program::

#include 
#include 
#include 

int data[100],data2[100];
int n;

void tukar(int a,int b)
{
 int t;
 t = data[b];
 data[b] = data[a];
 data[a] = t;
}

void selection_sort()
{
 int pos,i,j;
 for(i=0;i {
  pos = i;
  for(j = i+1;j  {
   if(data[j] < data[pos]) pos = j;
  }
  if(pos != i) tukar(pos,i);
 }
 cout<<"selection sort selesai!"< cout<<"Silahkan klik enter kemudian pilih 4 untuk melihat hasilnya"<}


void insertion_sort()
{
 int temp,i,j;
 for(i=1;i {
  temp = data[i];
  j = i -1;
  while(data[j]>temp && j>=0)
  {
   data[j+1] = data[j];
   j--;
  }
  data[j+1] = temp;
 }
 cout<<"insertion sort selesai!"< cout<<"Silahkan klik enter kemudian pilih 4 untuk melihat hasilnya"<}

void Input()
 {
 cout<<"Masukkan jumlah data = "; cin>>n;
 for(int i=0;i {
  cout<<"Masukkan data ke-"<<(i+1)<<" = "; cin>>data[i];
  data2[i] = data[i];
 }
}


void Tampil()
{
 cout<<"Data : "< for(int i=0;i {
  cout< }
 cout<}

void AcakLagi()
{
 for(int i=0;i {
  data[i] = data2[i];
 }
 cout<<"Data sudah teracak!"< cout<<"Silahkan klik enter kemudian pilih 4 untuk melihat hasilnya"<}

void main()
{
 int pil;
 clrscr();
 do
 {
  clrscr();
  cout<<"+++++++++++++++Program Sorting+++++++++++++++"<  cout<<"*********************************************"<  cout<<" 1. Input Data"<  cout<<""<  cout<<" 2. Selection Sort"<  cout<<" 3. Insertion Sort"<  cout<<""<  cout<<" 4. Tampilkan Data"<  cout<<""<  cout<<" 5. Acak Data"<  cout<<""<  cout<<" 6. Exit"<  cout<<""<  cout<<"    Pilihan Anda = ";  cin>>pil;


switch(pil)
  {
   case 1:Input(); break;
   case 2:selection_sort(); break;
   case 3:insertion_sort(); break;
   case 4:Tampil(); break;
   case 5:AcakLagi(); break;
  }
  getch();
 }while(pil!=6);
}

Referensi:

1.  Utami, Ema.2007.Struktur Data Menggunakan C di GNU/Linux.Yogyakarta.Andi Publisher