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();
}Labels: Cplusplus
