cara kerja metode jenis insertion sort pada c++

SOBAT WINDOWS

1 Mar, 2021

Metode Insertion Sort

Metode Insertion Sort merupakan metode pengurutan dengan cara menyisipkan elemen array pada posisi yang tepat. Pencarian yang tepat dilakukan dengan melakukan pencarian beruntun di dalam array. Selama pencarian posisi yang tepat dilakukan pergeseran elemen array. Algoritma pengurutan ini tepat untuk persoalan menyisipkan elemen baru ke dalam array yang sudah terurut. Misalnya dalam permainan kartu, kartu yang dicabut biasanya disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurut.

Misalkan kita memiliki suatu array dengan N maka pengurutan secara menaik dengan metode Insertion Sort sebagai berikut:

Langkah -1: elemen pertama Nilai[0] diasumsikan telah sesuai tempatnya.

Langkah -2: ambil elemen ke dua (Nilai[1]), cari lokasi yang tepat pada Nilai[0..0] untuk Nilai Nilai[1]. Lakukan pergeseran ke kanan jika Nilai[0..1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[1]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[1] pada Nilai[j].

Langkah -3: ambil elemen ke tiga (Nilai[2]), cari lokasi yang tepat pada Nilai[0..1] untuk Nilai[2]. Lakukan pergeseran ke kanan jika Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[2]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[2] pada Nilai[j].

Langkah -4: ambil elemen ke empat (Nilai[3]), cari lokasi yang tepat pada Nilai[0..3] untuk Nilai Nilai[3]. Lakukan pergeseran ke kanan jika Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[3]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[3] pada Nilai[j].

…

Langkah –N: ambil elemen ke N (Nilai[N]), cari lokasi yang tepat pada Nilai[0..N-1] untuk Nilai Nilai[N]. Lakukan pergeseran ke kanan jika Nilai[0..N-1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[N]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[N] pada Nilai[j].

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Insertion Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:

Langkah -1: Nilai[0] diasumsikan telah terurut.

Langkah -2: cari lokasi yang tepat untuk Nilai[1] pada Nilai[0..0]. Dalam hal ini, ternyata 72 tidak lebih besasr dari 25 maka tidak terjadi pergeseran, sehingga diperoleh array seperti berikut:

Langkah -3: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] digeser ke kanan sehingga Nilai[2] di posisi ke 1, sehingga diperoleh array sebagai berikut:

Langkah -4: cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2]. Dalam hal ini, ternyata lokasi yang tepat adalah 2, maka Nilai[2] digeser ke kanan sehingga Nilai[3] di posisi ke 3, sehingga diperoleh array seperti berikut:

Langkah -5: cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3] digeser masing-masing satu posisi ke kanan sehingga Nilai[4] di posisi ke 0, sehingga array seperti berikut:

Langkah -6: cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3] dan Nilai[4] digeser masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array seperti berikut:

Langkah -7: cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3], Nilai[4] dan Nilai[5] digeser masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array seperti berikut:

Langkah -8: cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6]. Dalam hal ini, ternyata lokasi yang tepat adalah 6, maka Nilai[6] digeser satu posisi ke kanan sehingga Nilai[7] di posisi ke 6, diperoleh array seperti berikut:

Selesai. Dan array telah terurut secara menaik. Program untuk mengurutkan elemen array secara menaik dengan metode Insertion Sort dapat dilihat pada program Lat_Sorting_07a.

/* Program Pengurutan Metode Insertion Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_07a */
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
  int Nilai[20];
  int i, j, k, N;
  int temp;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
    
  //Proses Pengurutan
  for(i=1; i<N; i++)
  {
    temp = Nilai[i];
    j=i-1;
    while((temp <= Nilai(j)) && (j>=1))
    {
      Nilai[j+1] = Nilai[j];
      j--;
    }
    if(temp >= Nilai[j])
      Nilai[j+1] = temp;
    else
    {
      Nilai[j+1] = Nilai[j];
      Nilai[j] =  temp;
    }
    cout<<endl;
    for(k=0; k<N; k++)
      cout<<setw(3)<<Nilai[k];
  }
  
  //Proses Cetak Setelah diurutkan
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  getch();
}

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menurun dengan metode Insertion Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:

Langkah -1: Nilai[0] diasumsikan telah terurut

Langkah -2: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..0]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0] digeser ke kanan satu posisi dan Nilai[1] menempati posisi ke 0, sehingga diperoleh array seperti berikut:

Langkah -3: cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] digeser satu posisi ke kanan sehingga Nilai[2] di posisi ke 1, sehingga diperoleh array seperti berikut:

Langkah -4: cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] dan Nilai[2] digeser satu posisi ke kanan sehingga Nilai[3] di posisi ke 1, sehingga diperoleh array seperti berikut:

Langkah -5: cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3]. Dalam hal ini, ternyata lokasi yang tepat adalah 4, tapi karena oleh dirinya sendiri maka tidak ada pergeseran, sehingga array seperti berikut:

Langkah -6: cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4]. Dalam hal ini, ternyata lokasi yang tepat adalah 5, tapi karena oleh dirinya sendiri maka tidak ada pergeseran, sehingga array seperti berikut:

Langkah -7: cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5]. Dalam hal ini, ternyata lokasi yang tepat adalah 6, tapi karena oleh dirinya sendiri maka tidak ada pergeseran, sehingga array seperti berikut:

Langkah -8: cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1], Nilai[2], Nilai[3], Nilai[4], Nilai[5], Nilai[6] digeser satu posisi ke kanan sehingga Nilai[7] di posisi ke 1, diperoleh array seperti berikut:

Selesai. Dan array telah terurut secara menaik. Program untuk mengurutkan elemen array secara menaik dengan metode Insertion Sort dapat dilihat pada program Lat_Sorting_07a.

/* Program Pengurutan Metode Insertion Sort
  Pengurutan Secara Menurun
  Nama File : Lat_Sorting_07b */
#include<iostream.h>
#include<conio.h>
#inlcude<iomanip.h>
void main()
{
  int Nilai[20];
  int i, j, k, N;
  int temp;
  //bool ketemu;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
    
  //Proses Pengurutan
  for(i=1; i<N; i++)
  {
    temp = Nilai[i];
    j=i-1;
    while((temp > Nilai[i]) && (j>=1))
    {
      Nilai[j+1] = Nilai[j];
      j--;
    }
    if(temp <= Nilai[j])
      Nilai[j+1] = temp;
    else
    {
      Nilai[j+1] = Nilai[j];
      Nilai[j] = temp;
    }
    cout<<endl;
    for(k=0; k<N; k++)
      cout<<setw(3)<<Nilai[k];
  }
  
  //Proses Cetak Setelah diurutkan
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  getch();
}