Metode Pemograman Algoritma Insertion Sort

Pengurutan dengan penyisipan (insertion sort) adalah suatu metode yang melakukan pengurutan dengan cara menyisipkan data yang belum urut ke dalam bagian data yang telah diurutkan. Konsep ini biasa dilakukan pada permainan kartu. Ketika sebuah kartu baru didapatkan (hasil pembagian dari pengocokan kartu) kartu akan disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurutkan.

Mengurutkan kartu dengan metode penyisipan kartu 7 disisipkan sehingga susunan kartu yang sebelumnya sudah urut tetap urut

"Bila L adalah larik dengan n elemen, mula-mula L[0] (elemen pertama) dianggap sebagai kumpulan data yang telah diurutkan, yang terdiri atas 1 buah data. Kemudian dilakukan penyisipan data dari L[1] sampai dengan L[n-1] ke dalam kumpulan data dari L[0] sampai dengan L[k-1] dengan 1<= k < n. Dalam hal ini penyisipan dilakukan pada tempat yang tepat sehingga data pada L[0] sampai dengan L[k] menjadi urut."

Algoritma : 

SUBRUTIN selection_sort (L,n)

UNTUK k <-- 1 S/D n-1

X <--L[k]

//Sisipkan x ke dalam L[0..k-1]

I<-- k – 1

Ketemu <-- SALAH

ULANG SEMUA I >= 0 DAN TIDAK ketemu

JIKA x < L[I] MAKA

L[i + 1] <-- L[i]

i <--i – 1

SEBALIKNYA 

Ketemu = BENAR

AKHIR – JIKA

L[i+1]<--x

AKHIR – ULANG

AKHIR – UNTUK 

AKHIR – SUBRUTIN

Implementasi ke dalam program c++

#include <iostream.h>

#include <conio.h>

void tampilkan_larik(int data[],int n)

{

int i;

for (i=0; i<n;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

void insertion_sort(int data[], int n)

{

int i,k;

int x;

int ketemu;

for (k=1; k<n; k++)

{

x=data[k];

//sisipkan x ke dalam data [0...k-1]

i=k-1;

ketemu=0;

while ((i>=0)&&(!ketemu))

{

if (x<data[i])

{

data[i+1]=data[i];

i=i-1;

}

else

ketemu=1;

data[i+1]=x;

}

}

}

int main()

{

const jum_data=8;

int i;

int data[]={25,57,48,37,12,92,80,33};

cout<<"Data sebelum diurut: "<<endl;

for(int ctr=0; ctr<8; ctr++)

{

cout<<data[ctr]<<" ";

}

insertion_sort(data, jum_data);

//hasil pengurutan

cout<<endl;

cout<<endl;

cout<<"Tampilkan Hasil Pengurutan: \n";

tampilkan_larik(data,jum_data);

getch();

}

Sumber: http://allaboutalgoritma.blogspot.co.id/2009/06/pengurutan-dengan-penyisipan-insertion.html