Pengertian Insertion Sort dan Implementasinya Kedalam Koding

by Simpan Gambar Aja 03.02 0 komentar C++ Pemrograman

Metode Insertion Sort merupakan metode pengurutan dengan cara menyisipkan elemen array pada posisi yang tepat. Pencarian yang dapat dilakukan dengan melakukan pencarian beruntun didalam 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 yangdicabut biasanya disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurut.

            Misalkan kita memilii 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 Nila[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 yang menaik) atau lebih kecil (untuk urut yang menurun) dari Nilai[2]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[2] pada Nilai[j].

-          Langkah -4: ambil elemen ke N (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 posisis yang tepat adalah j, maka sisipkanlahNilai[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..2] 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 kodingnya adalah seperti berikut:

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

using namespace std;

int main()
{
    //Mendeklarasikan array dengan 7 buah elemen
    //Yang bertipe integer
    int A[7];

    //Mendeklarasikan variable-variabel bantu
    //Yang diperlukan
    int i,j,c,temp;

    //Memasukan Nilai array
    cout<<"Menginputkan Nilai Kedalam Elemen Array!!"<<endl;
    cout<<"========================================="<<endl;
    for(c=0;c<7;c++)
    {
        cout<<"A["<<c<<"] :";
        cin>>A[c];
    }

    cout<<endl<<endl;

    //Menapilkan Elemn Array Sebelum Di Urutkan
    cout<<"Elemen Array Sebelum Di Urutkan"<<endl;
    cout<<"==============================="<<endl;
    for(c=0;c<7;c++)
    {
        cout<<"A["<<c<<"]: "<<A[c]<<endl;
    }

     cout<<endl<<endl;

    //Melakukan pengurutan Elemen Array
    //Dengan metode Insertion sort

   for(c=1;c<7;c++)
   {
       temp=A[c];
      j=c-1;
      while(A[j]>temp && j>=0)
      {
           A[j+1]=A[j];
         j--;
      }
      A[j+1]=temp;
   }

    //Menampilkan Nilai array setelah di urutkan
    cout<<"Nilai Elemen Array Setalah Diurutkan!!"<<endl;
    cout<<"======================================"<<endl;
    for(c=0;c<7;c++)
    {
        cout<<"A["<<c<<"]: "<<A[c]<<endl;
    }

    getch();
    return 0;
}

Jika di Compile koding di atas akan tampak seperti gambar di bawah ini:

Sumber  : Buku Konsep dan Implementasi Struktur Data Dengan C++

Oleh       : Lamhot Sitorus dan David J.M. Sembiring

Penerbit  : Andi