Septian Purwandi: Insertion Sort

Insertion Sort

Insertion Sort (Metode Penyisipan)

---( Straight Insertion Sort (Metode Penyisipan langsung)

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.

Animation of the insertion sort sorting a 30 element array.

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

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;
} }

---( Binary Insertion Sort (Metode Penyisipan Biner)

Metode ini merupakan pengembangan dari metode penyisipan langsung. Dengan cara penyisipan langsung, perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i- 1 kali. Ide dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i, data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut.

Algoritma penyisipan biner dapat dituliskan sebagai berikut :

1. i = 1
2. selama (i < N) kerjakan baris 3 sampai dengan 14
3. x = Data[i]
4. l = 0
5. r = i – 1
6. selama (l<=r) kerjakan baris 7 dan 8
7. m = (l + r) / 2
8. jika (x < Data[m]) maka r = m – 1, jika tidak l = m + 1
9. j = i – 1
10. selama ( j >=l) kerjakan baris 11 dan 12
11. Data[j+1] = Data[j]
12. j = j – 1
13. Data[l] = x
14. I = i + 1

Di bawah ini merupakan prosedur yang menggunakan metode penyisipan biner:

void BinaryInsertSort()
{
int i, j, l, r, m, x;
for (i=1; i<Max; i++){
x = Data[i];
l = 0;
r = i - 1;
while(l <= r){
m = (l + r) / 2;
if(x < Data[m])
r = m - 1;
else
l = m + 1;
}
for(j=i-1; j>=l; j--)
Data[j+1] = Data[j];
Data[l]=x;
}
}