Selection sort dan Insertion sort

SELECTION SORT

Merupakan sebuah metode pengurutan. Memindahkan elemen dengan cara membandingkan elemen sekarang dengan elemen yang berikutnya sampai dengan elemen terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar dan begitu seterusnya.

Proses pada selection sort:

 -    Mencari data terkecil dari data pertama sampai dengan data yang terakhir. kemudian ditukar posisinya dengan data pertama.

 -    Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian ditukar posisinya dengan data kedua.

 -    Mencari data terkecil dari data ketiga sampai dengan data terakhir, kemudian ditukar posisinya dengan data ketiga.

 -    Begitu seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1) langkah pengurutan, dengan data terakhir, yaitu data ke n tidak perlu diurutkan karena hanya tinggal data satu-satunya.

Contoh

Terdapat suatu variable array dimana nilai dalam array tersebut :

NILAI[8] = { 44, 55, 12, 42, 94, 18, 6, 67 }

Penyelesaian

 INSERTION SORT

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pososinya dengan cara melakukan perbandingan dengan data – data yang ada. Algoritma ini akan mudah anda kuasi jika sering bermain Game Remi, Domino, Main Minum, dll. Ide algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu. Jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. 

Contoh Algoritmanya:

Data awal sebelum di urutkan, asumsi pertama anggaplah data indek ke- sudah benar

Data awal sebelum di urutkan, asumsi pertama anggaplah data indek ke-0 sudah benar

Step 1

Bandingkan data index ke 0 dan ke 1, Jika data index ke 1 lebih kecil, datanya ditukar

Step 2

Bandingkan data index ke 2 dengan ke 1 dan 0, Jika lebih kecil, selipkan pada posisi yang tepat

Step 3

Bandingkan data index ke 3 dengan data didepannya. Jika lebih kecil, selipkan pada posisi yang tepat. Jika tidak biarkan data tersebut

Step 4

Bandingkan data index ke 4 dengan data didepannya. Jika lebih kecil, selipkan pada posisi yang tepat. Data yang lain akan mundur posisinya, karena ada data yang maju.

Step 5

Bandingkan data index ke 5 dengan data didepannya. Jika lebih kecil, selipkan pada posisi yang tepat. Data yang lain akan mundur posisinya, karena ada data yang maju.

Contoh Programnya :

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

int data[10],data2[10];
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<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;
}

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;
}

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];
   }
}


void main()
{
 int pil;
   clrscr();
   do
   {
      clrscr();
    cout<<"1. Input Data"<<endl;
    cout<<"2. Selection Sort"<<endl;
    cout<<"3. Insertion Sort"<<endl; //tambahkan
    cout<<"4. Exit"<<endl;
      cout<<"Masukkan Pilihan anda = ";
      cin>>pil;

    switch(pil)
    {
       case 1: input();break;
       case 2: selection_sort();break;
       case 3: insertion_sort();break;  //tambahkan
    }
    getch();
   }
   while(pil!=4);
}

Hasil Outputnya :