Metode Penyisipan Langsung (Straight Insertion Sort)

Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :

Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu.

Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

Algoritma penyisipan langsung dapat dituliskan sebagai berikut :

1 i ← 1

2 selama (i < N) kerjakan baris 3 sampai dengan 9

3 x ← Data[i]

4 j ← i – 1

5 selama (x < Data[j]) kerjakan baris 6 dan 7

6 Data[j + 1] ← Data[j]

7 j ← j – 1

8 Data[j+1] ← x

9 i ← i + 1

Untuk lebih memperjelas langkah-langkah Algoritma Penyisipan Langsung dapat dilihat pada tabel contoh. Proses pengurutan pada tabel dapat dijelaskan sebagai berikut:

Tabel Contoh

Di bawah ini merupakan prosedur yang menggunakan metode penyisipan langsung.

void StraighInsertSort()

{

int i, j, x;

for(i=1; i<Max; i++){

x = Data[i];

j = i - 1;

while (x < Data[j]){

Data[j+1] = Data[j];

j--;

}

Data[j+1] = x;

}

}

Prosedur Pengurutan dengan Metode Penyisipan Langsung

Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) minimum, rata-rata dan maksimum pada metode penyisipan langsung adalah :

Cmin = N – 1

Crata-rata = (N2 + N + 2) / 4

Cmax = (N2 + N – 2) / 2

Jumlah perbandingan minimum terjadi jika data sudah dalam keadaan urut, sebaliknya jumlah perbandingan maksimum terjadi jika data dalam keadaan urut terbalik.

Cara menghitung Cmin adalah dengan melihat kalang paling luar yaitu i,

pengulangan ini dimulai dari 1 sampai dengan N-1 atau sama dengan N-1

Cara menghitung Cmax dengan menganggap selalu terjadi pergeseran. Kalang

dalam (while) diatas akan melakukan pengulangan dari 0 sampai dengan i. Apabila hal ini dilakukan sebanyak N-1 kali, maka Cmax adalah jumlah dari deret aritmetik 2, 3, 4, ..., N

atau (N – 1) / 2 . (2 + N)

Cara menghitung Crata-rata adalah dengan menjumlahkan Cmin dan Cmax dan dibagi dengan 2.

Jumlah penggeseran (=M) minimum, rata-rata dan maksimum untuk metode

penyisipan langsung adalah :

Mmin = 2(N – 1)

Mrata-rata = (N2 + 7N - 8) / 4

Mmax = (N2 + 3N – 4) / 2