Sorting dan Searching Data Dalam C++

5. Sorting.

Sorting atau pengurutan diartikan sebagai proses penyusunan kembali sekumpulan objek ke dalam urutan tertentu. Tujuan pengurutan adalah mendapatkan kemudahan dalam pencarian anggota dari suatu himpunan, disamping dapat mempercepat mengetahui data terbesar dan data terkecil, misalkan kita ingin mengetahui perolehan nilai tertinggi dan nilai terendah dari hasil ujian. Contoh objek terurutkan adalah daftar isi, daftar pustaka dll. Proses yang terjadi pada pengurutan adalah sebagai berikut :

1. Perbandingan data.
2. Pengurutan data.

Metode Selection Sort

Metode Selection Sort proses pengurutan secara ascending :

1. Mencari data terkecil dengan cara membandingkan data pertama dengan data kedua sampai data terakhir, jika ditemukan data yang lebih kecil antara data kedua hingga data terakhir daripada data pertama, maka terjadi pertukaran data. Jika tidak, maka tidak terjadi pertukaran data.
2. Mencari data terkecil dengan cara membandingkan data kedua dengan data ketiga sampai data terakhir, jika ditemukan data yang lebih kecil antara data ketiga hingga data terakhir daripada data kedua, maka terjadi pertukaran data. Jika tidak, maka tidak terjadi pertukaran data.
3. Dan Seterusnya. Jika ada n buah data yang akan diurutkan, maka langkah pengurutan yang perlu dilakukan sebanyak (n-1) langkah karena data ke-n tinggal satu – satunya.

Implementasi Pada Program (Borlan C++):

//Preprosesor
#include<iostream>
#include<conio.h>

//deklarasi variabel;
int n,pilihan,data[10],data2[10];

//deklarasi fungsi-fungsi
void input();
void selection_sort();
void tukar(int a, int b);

//fungsi main program
void main()
{
   clrscr();
   do
   {
    cout<<"1. Input Data"<<endl;
    cout<<"2. Selection Sort"<<endl;
    cout<<"3. Exit"<<endl;
    cout<<"Masukkan Pilihan anda = ";
    cin>>pilihan;

    switch(pilihan)
    {
       case 1:
          input();
         break;

       case 2:
          selection_sort();
         break;
    }
    getch();
   }
   while(pilihan!=3);
}

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

// fungsi selection sort
void selection_sort()
{
   int pos,i,j;
   for(i=0;i<n-1;i++)
   {
      pos=i;
      for(j=i+1;j<n;j++)
      {
       if(data[j]<data[pos])pos=j;
      }
      if(pos!=i) tukar(pos,i);
   }
   cout<<"selection sort selesai !"<<endl;
   cout<<"Data : "<<endl;
   for(int i=0;i<n;i++)
   {
    cout<<data[i]<<" ";
   }
   cout<<endl<<endl;
}

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

Hasil Eksekusi Program:

Metode Insertion Sort

Metode Insertion Sort pada prosesnya mengurutkan data yang dimulai dari dari data ke-2, lalu diletakkan pada posisi yang sesuai. Untuk data pertama diumpamakan sudah sesuai dengan posisinya.

Implementasi Pada Program (Borlan C++):

//Preprosesor
#include<iostream>
#include<conio.h>

//deklarasi variabel;
int n,pilihan,data[10],data2[10];

//deklarasi fungsi-fungsi
void input();
void insertion_sort();
void tukar(int a, int b);

//fungsi main program
void main()
{
   clrscr();
   do
   {
    cout<<"1. Input Data"<<endl;
    cout<<"2. Selection Sort"<<endl;
    cout<<"3. Exit"<<endl;
    cout<<"Masukkan Pilihan anda = ";
    cin>>pilihan;

    switch(pilihan)
    {
       case 1:
          input();
         break;

       case 2:
          insertion_sort();
         break;
    }
    getch();
   }
   while(pilihan!=3);
}

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

// fungsi insertion sort
void insertion_sort()
{
   int temp,i,j;
   for(i=1;i<n;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 ! "<<endl;
   cout<<"Data : "<<endl;
   for(int i=0;i<n;i++)
   {
    cout<<data[i]<<" ";
   }
   cout<<endl<<endl;
}

Hasil Eksekusi Program:

6. Searching
Searching atau pengurutan merupakan metode pencarian data dalam suatu array, baik yang sudah terurut maupun yang belum terurut. Ada 2 metode yang dapat digunakan diantaranya: Squential Search dan Binary Search.

Sequential Search
Sequential Search atau pencarian secara berurutan dilakukan dengan cara memeriksa elemen laarik satu per satu mulai dari indeks=0 hingga indeks dimana elemen tersebut ditemukan. Bila indeks maksimum telah dilampaui berarti elemen tersebut tidak ditemukan.

Implementasi Pada Program (Borlan C++):

//Preprosesor
#include<stdio.h>
#include<iostream.h>
#include<conio.h>

//fungsi main program
void main()
{
 //deklarasi variabel
 int Arrdata[20],index[20],n,i,j,k;

 //proses penginputan data
 cout<<"Masukkan jumlah data [Max 20] : ";
 cin>>n;

 for(i=0;i<n;i++)
 {
      cout<<"Masukkan Data ke - "<<(i+1)<<" : ";
      cin>>Arrdata[i];
 }

 //memasukkan data yang akan dicari ke dalam K
 cout<<"Masukkan data yang anda akan cari : ";
 cin>>k;

 //proses pencarian data
 j=0;
 for (i=0;i<n;i++)
 {
  if(Arrdata[i]==k)
  {
   index[j]=i;
   j++;
  }
 }

 //jika data ditemukan dalam array
 if (j>0)
 {
  cout<<"Data" <<k<< "yang dicari ada" <<j<< "buah"<<endl;
  cout<<"Data tersebut terdapat dalam index ke : ";
    for(i=0;i<j;i++)
  {
         cout<<index[i]<<" ";
  }
  cout<<endl;
 }

 //jika tidak ditemukan
 else
 {
      cout<<"Data tidak ditemukan dalam array"<<endl;;
 }
 getch();
}

Hasil Eksekusi Program:

Binary Search
Binary Search atau pencarian bagi-dua adalah teknik yang diterapkan hanya pada elemen array yang telah terurut (sorted). Pencaria beruntun memiliki satu kekurangan yaitu dalam pencarian elemen yang sama pada suatu data, maka yang ditemukan cuman satu elemen saja.

Implementasi Pada Program (Borlan C++):

//Preprosesor
#include<stdio.h>
#include<conio.h>
#include<iostream.h>

//fungsi main program
void main()
{
 //deklarasi variabel
 int Arrdata[20],n,i,j,k,tukar,kanan,kiri,tengah,tm;

 //proses penginputan data
 cout<<"Masukkan jumlah data [max 20] : ";
 cin>>n;
 for(i=0;i<n;i++)
 {
      cout<<"Masukkkan data ke - "<<(i+1)<<" : ";
      cin>>Arrdata[i];
 }
 cout<<"Masukkan data yang akan anda cari :";
 cin>>k;

 //proses pengurutan data
 for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
  {
   if (Arrdata[i]>Arrdata[j])
   {
    tukar=Arrdata[i];
    Arrdata[i]=Arrdata[j];
    Arrdata[j]=tukar;
   }
  }
 }

 //proses pencarian data
 tm=0;
 kanan=n;
 kiri=0;
 while(kanan>=kiri)
 {
  tengah=(kanan+kiri)/2;
  if(Arrdata[tengah]==k)
  {
   tm++;
  }
  if(Arrdata[tengah]<k)
  {
   kiri=tengah+1;
  }
  else
  {
   kanan=tengah-1;
  }
 }
 if (tm>0)
 {
  cout<<"Data " << k << " yang dicari ada dalam array"<<endl;
 }
 //jika tidak ditemukan
 else
 {
 cout<<"Data tidak ditemukan dalam array"<<endl;
   }
   getch();
}

Hasil Eksekusi Program:

Referensi:
Suarga (2004), Algoritma Pemrograman, ANDI Publisher
Fachrurrozi (2006), Modul Struktur Data, Universitas Sriwijaya
Utami, Ema (2009), 10 Langkah Belajar Logika dan Algoritma Menggunakan Bahasa C dan C++, ANDI Publisher