Metode penyisipan ( insertion sort )

Metode penyisipan ( insertion sort )

Pengurutan dengan metode ini dimulai dengan membandingkan harga data pada urutan kedua terhadap data urutan pertama, jika data kedua lebih besar maka posisinya ditukar dengan data pertama, pada langkagh berikutnya data pada urutan ketiga dibandingkan dengan data urutan kedua jika data ketiga lebih besar maka posisinya ditukar dengan data kedua, kemudian data tersebut dibandingkan dengan data pertama jika lebih besar maka ditukar dengan data pertama.

misalkan larik L dengan n=6 sebagai berikut

25	27	10	8	76	21
1	2	3	4	5	6

maka langkah-langkah pengurutannya adalah:

Semula	29	27	10	8	76	21
Iterasi 1	27	29	10	8	76	21
Iterasi 2	10	27	29	8	76	21
Iterasi 3	8	10	27	29	76	21
Iterasi 4	8	10	27	29	76	21
Iterasi 5	8	10	27	29	76	21
Iterasi 6	8	10	21	27	29	76

Procedure InsertionSort(input/output L : Larikint, input N : integer)

{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode

pengurutan sisip}

{k.awal : elemen-elemen larik L sudah terdefinisi nilainya}

{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] _ L[2] _ ...

_ L[N]}

I : integer

J : integer {pencacah untuk mencari nilai maksimum}

Y : integer {peubah boolean untuk menyatakan posisi penyisipan ditemukan}

Ketemu : boolean

Deskripsi

{elemen L[1] dianggap sudah terurut}

For I _ 2 to N do {mulai dari langkah 2 sampai langkah N}

{sisipkan L[I] ke dalam bagian yang sudah terurut}

Y _ L[I]

{cari posisi yang tepat untuk Y di dalam L[1..I-1] sambil menggeser}

J _ I – 1

Ketemu _ false

While (J_1) and (not Ketemu) do

If Y < L[J] then

L[J+1] _ L[J]

J _ J – 1

Else

Ketemu _ true

Endif

Endwhile

{J < 1 or Ketemu}

L[J+1] _ Y {sisipkan Y pada tempat yang sesuai}

Endfor