Sorting

Struktur Data - Pertemuan 18

"Sorting"

Pengertian Sorting

Sorting adalah  sesuatu proses aplikasi dimana yang awalnya acak -acakkan lalu diurutkan dalam sebuah sekumpulan objek menurut urutan atau susunan sesuai dengan kebutuhan agar ketata rapi. Tujuan dari penggunaan sorting adalah memudahkan seseorang dalam pencarian, menyusun data yang awalnya acak – acakkan menjadi keurut, dan menyeselaikan masalah yang kompleks seperti schedulling, pengolahan basis data dan lain – lain.

Dua Macam Pengurutan

Ø  Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.

Ø  Descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

Sebagai contoh misalkan diberikan data berupa bilangan berikut ini:
3   9   1   4   0   2

Hasil sorting:

Ø   Ascending adalah 0  1   2   3   4   9

Ø  Descending adalah 9   4   3   2   1   0.

Berdasarkan media yang digunakan terdapat 2 metode sortir :

1. Sortir Internal

Metode ini dipakai jika himpunan data yang akan disortir kecil, sehingga proses sortir tidak membutuhkan tempat yang besar di memori utama komputer.

2. Sortir Eksternal

Metode ini dipakai jika himpunan data yang akan disortir cukup besar, sehingga dibutuhkan media atau alat tambahan seperti Magnetik Tape, Disket dan sebagainya.

Dua hal yang mempengaruhi kecepatan algoritma sortir adalah :

1. Jumlah operasi perbandingan yang dilakukan.

2. Jumlah operasi pemindahan data dilakukan.

Jenis Jenis Sorting

A. Bubble Sort

Adalah pengurutan yang dilakukan dengan membandingkan apakah data sebelum dengan sesudahnya mana yang lebih besar atau kecil lalu ditukarkan secara terus menerus sampai data tersebut kesusun menurut perintah yang dilakukan apakah secara ascending atau descending.

Kelebihan

• Mudah dipahami karena algoritma pengurutannya yang simpel

Kekurangan

• Lambat dalam pengurutan dengan data dengan jumlah yang lebih besar
• Memakan waktu yang lama karena harus membandingkan data satu persatu meskipun ada yang sudah terurut

Proses pengurutan menggunakan Bubble Sort

• Pertama membandingkan data ke – i dengan data  ke (i+1).Jika tidak sesuai dengan kententuan urutan apakah ascending atau descending maka tukar.
• Terus bandingkan data sampai ke data yang terakhir .
• Proses akan terhenti bila membandingkan data sampai data yang terakhir.

Contoh : Apabila terdapat daftar angka 390, 205, 182, 45, 235, lakukan sorting dengan Teknik Bubble Sort.

B. Selection Sort

Adalah pengurutan yang dilakukan dengan cara mencari nilai maksimum atau minimum yang dimulai dari data posisi 0 hingga ke posisi N-1. Ada 2 cara pengurutan di dalam selection sort yaitu seleksi maksimum dan minimum .Seleksi maksimum adalah memilih elemen maksimum sebagai pengurutan sedangkan seleksi minimum  adalah memilih elemen minimum sebagai pengurutan.

Kelebihan

• Operasi pentukaran hanya sekali saja
• Tidak memakan waktu yang lama

Kekurangan

• Sulit dalam membagi masalah

Proses pengurutan menggunakan Selection Sort

• Mencari data terkecil dalam interval j=0 sampai j=N-1.
• Jika pada posisi posditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k. dan ulangi sampai data sudah keurut.

Contoh bila diketahui list angka 390, 205, 182, 45, 235 dilakukan sorting dengan teknik Selection Sort.

C. Insertion Sort

Adalah pengurutan yang dilakukan dengan cara menyisipkan elemen pada posisi yang sudah ditentukan atau tepat .

Kelebihan

• Stabil
• Penerapannya yang sederhana
• Pengurutan data yang tercepat dalam jumlah elemen yang sedikit

Kelemahan

• Banyak operasi yang dilakukan dalam mencari posisi elemen yang tepat
• Untuk data dalam jumlah besar tidak praktis

Contoh : untuk list angka yang sama seperti diatas, yaitu : 390, 205, 182, 45, 235 lakukan Sorting dengan teknik Insertion Sort

Program menu sorting :

#include<time.h>
#include<iostream>
#include<conio.h>
#include<windows.h>

using namespace std;
int main() {
 
 int pil;
cout << "======= Program Sorting (Bubble, Insertion, Selection) =========="<<endl<<endl;
cout << "1. Bubble sort" <<endl;
cout << "2. Insertion sort" <<endl;
cout << "3. Selection sort" <<endl<<endl;
cout << "==============================="<<endl<<endl;

cout << "Masukan pilihan anda = "; cin >> pil;

switch(pil) {
 
 
 
 ////////////////////////////////////

 ////  Buble start /////////////

 ////////////////////////

 case 1:
 system("cls");
 cout << endl;
 cout << "Bubble sort"<<endl;
 cout << "=============="<<endl;
 
 int t1,t2;
 
    int hold;
 int array[5];

 cout<<"Masukan 5 angka :"<<endl;

 for(int i=0; i<5; i++) {
  cout << "  angka ke " <<i+1 <<" = ";cin>>array[i];
 }
 cout<<endl;
 cout<<endl;
 t1=GetTickCount();
 cout<<"Sebelum di sortir = ";

 for(int j=0; j<5; j++) {
 cout<<array[j];
 cout<<"  ";
 }
 
 cout<<endl;
 
 cout <<endl<< "Urutan program"<<endl;
 for(int i=0; i<4; i++) {
  for(int j=0; j<4; j++) {
   if(array[j]<array[j+1]) {
    hold=array[j];
    array[j]=array[j+1];
    array[j+1]=hold;
    
    for(int i=0; i<5; i++) {
  cout<<array[i]<<"  ";
  }
  cout<<endl;
   }
  
  
  }
  
 }
cout<<endl;
 cout<<"Setelah di sortir = ";

 for(int i=0; i<5; i++) {
  cout<<array[i]<<"  ";
 }
    cout<<endl;
 t2=GetTickCount();
 cout << endl <<"Lama proses = " << (int)(t2 - t1) << " ms";
 cout<<endl;
 
 break;


//////////////////////////////////////////////////////////

///////     Insertion start               /////////

////////////////////////////////////////////////


 
 case 2:
 system("cls");
 cout << "Insertion sort";
 cout <<endl<<"============="<<endl;
 cout<<endl;
 int t3,t4;
 
 int Key;
 int array1[5];

 cout<<"Masukan 5 angka : "<<endl;

for(int i=0; i<5; i++)  {
 cout << "  angka ke " <<i+1 <<" = ";cin>>array1[i];
}

cout<<endl;
t3=GetTickCount();
cout<<"Angka sebelum di sortir = ";

for(int j=0; j<5; j++) {
 cout<<array1[j]<<"  ";
 
}

cout<<endl;
cout<<endl<< "Data proses "<<endl;
for(int j=1 ; j < 5 ; j++) {
 Key = array1[j];              
 int i = j-1;                  
 while(i >= 0 && array1[i] < Key) {
  array1[i + 1] = array1[i];
  i = i - 1;
 }
 array1[i + 1] = Key;
 
 for(int l=0; l<5; l++) {
  cout<<array1[l]<<"  ";
  
 }
 cout<<endl;
}
cout<<endl<<"Angka setelah disortir = ";

for(int i=0; i<5; i++) {
 cout<<array1[i]<<"  ";
 
}
t4=GetTickCount();
cout << endl<<endl <<"Lama proses = " << (int)(t4 - t3) << " ms";
 cout<<endl;

 break;
 
 
 
////////////////////////////////////////////////////////

//////////////   Selection start /////////////////////

/////////////////////////////////////
 
 
 case 3:
 system("cls");
 cout << "Selection sort";
 cout <<endl<< "================="<<endl<<endl;
 int t5,t6;
 int arr[5];
int mini,temp;

cout<<"masukan 5 angka ="<<endl;

for(int i=0; i<5; i++) {
 cout << "  angka ke " <<i+1 <<" = ";cin>>arr[i];
}
t5=GetTickCount();
cout<<endl;
cout<<"Angka sebelum di sortir = ";

for(int j=0; j<5; j++) {
 cout<<arr[j]<<"  ";
 
}

for(int r1=0;r1<4;r1++) {
 mini=r1;
 for(int r2=r1+1; r2<5; r2++)
   if(arr[r2]>arr[mini])
   mini=r2;
    if(mini !=r1) {
     temp=arr[r1];
     arr[r1]=arr[mini];
     arr[mini]=temp;
    }
}
cout<<endl;
cout<<endl;
cout<<"Setelah di sortir = ";
for(int q=0; q<5; q++) {
 cout<<arr[q]<< "  " ;
 
}
t6=GetTickCount();
cout << endl<<endl <<"Lama proses = " << (int)(t6 - t5) << " ms";
 cout<<endl;
 break;


//////////////////////////////////////////

//////           PILIHAN TIDAK ADA   /////////

//////////////////////////////////////////
 default:
 system("cls");
 cout << "Pilihan tidak ada";
 break;
 
}  
 
 
 
 getch();
}