Insertion sort

Insertion sort

 

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).
Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.

Demikian juga halnya dalam pengurutan data.
Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.
Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

Berikut adalah simulasi Algoritma Insertion Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Simulasi Insertion Sort

Dari gambaran proses pengurutan/ sorting  data di atas dapat diketahui  bagaimana data-data tersebut berpindah  posisi  dari satu index ke index lain dalam satu array.  Untuk detail proses pengurutan diatas, dapat disimak melalui detail simulasi berikut.
Data awal : 5, 2, 4, 6, 1, 3
Jumlah Index = 6   dimulai dari 0 s/d 5
Anggaplah index adalah ‘I’,
Untuk setiap proses pengurutan data, perbandingan data dimulai dari index kedua (dalam hal ini i=1)
Proses I:
i=1, x=1; j=0
x<j à2<5? — true  =2, 5, 4, 6, 1, 3
Proses II
i=2, j=1, x=2
x<j à  4<5 — true = 2, 4, 5, 6, 1, 3     j=j-1,      Jika benar    x=x-1
x<j à4<2 — false = 2, 4, 5, 6, 1, 3
Proses III
I=3, j=2, x=3
x<j à6<5 — false =  2, 4, 5, 6, 1, 3     j=j-1    jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena secara otomatis data yang ada disebelah kiri semuanya sudah terurut dengan benar.
Proses IV
i=4, j=3, x=4
x<j à1<6 — true = 2, 4, 5, 1, 6, 3   j=j-1,     jika benar  maka  x=x-1
x<j à 1<5 — true = 2, 4, 1, 5,6, 3  j=j-1 ,   jika benar  maka   x=x-1
x<j  à1<4  — true = 2, 1, 4, 5,6, 3  j=j-1,    jika benar  maka   x=x-1
x<j  à 1<2 — true =   1, 2, 4, 5,6, 3

Proses V
i=5, j=4, x=5
x<j à3<6  — true = 1, 2, 4, 5,3, 6  j=j-1, jika benar maka x=x-1
x<j à3<5 — true = 1, 2, 4, 3, 5, 6   j=j-1, jika benar maka x=x-1
x<j à3<4 — true = 1, 2, 3, 4, 5, 6  j=j-1, jika benar maka x=x-1
x<jà3<2 — false = 1, 2, 3, 4, 5, 6  j=j-1
Berikut adalah penerapannya di dalam program


#include<iostream>
#include <conio.h>
int main()
{
int data[]={5, 2, 4, 6, 1, 3};
cout<<”sebelum disorting: “;
for(int i=0; i<6; i++)
cout<<data[i] <<”,  “;
cout<<endl <<endl;
for(int i=1; i<6; i++)
{
int j=i;
while(data[j]<data[j-1])
{
int tmp=data[j];
data[j]=data[j-1];
data[j-1]=tmp;
j–;
}
}
cout<<”Setelah disorting: “;
for(int i=0; i<6; i++)
cout<<data[i] <<”,  “;
getch();
}