INSERTION SORT
A.
Definisi
Insertion sort adalah metode
pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.
B.
Macam- macam metode insertion sort
1.
LANGSUNG (STRAIGHT
INSERTION SORT)
Ilustrasi dari
langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight
insertion sort) dapat dilihat pada tabel berikut :
|
Iterasi
|
Data[0]
|
Data[1]
|
Data[2]
|
Data[3]
|
Data[4]
|
Data[5]
|
Data[6]
|
Data[7]
|
Data[8]
|
Data[9]
|
|
Awal
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
|
i=1
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
|
i=2
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
|
i=3
|
9
|
12
|
35
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
|
i=4
|
9
|
11
|
12
|
35
|
3
|
17
|
23
|
15
|
31
|
20
|
|
i=5
|
3
|
9
|
11
|
12
|
35
|
17
|
23
|
15
|
31
|
20
|
|
i=6
|
3
|
9
|
11
|
12
|
17
|
35
|
23
|
15
|
31
|
20
|
|
i=7
|
3
|
9
|
11
|
12
|
17
|
23
|
35
|
15
|
31
|
20
|
2. METODE PENYISIPAN BINER (BINARY
INSERTION SORT)
Metode pengurutan dengan algoritma penyisipan biner (binary
insertion sort) memperbaiki metode pengurutan dengan algoritma penyisipan
langsung dengan melakukan proses perbandingan yang lebih sedikit sehingga
proses pengurutan lebih cepat.
Metode penyisipan biner melakukan proses
perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengan i-1
yang disebut dengan bagian kiri dan kanan. Apabila data pada posisi ke i berada
pada jangkauan kiri maka proses perbandingan dilakukan hanya pada bagian kiri
dan menggeser posisi sampai i.
C.
Kelebihan dan kekurangan insertion
sort
-
Kelebihan
1.
Sederhana dalam penerapannya.
2.
Mangkus dalam data yang kecil.
3.
Jika list sudah terurut atau sebagian terurut maka
Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.
4.
Mangkus dalam data yang sebagian sudah terurut.
5.
Lebih mangkus dibanding Bubble Sort dan Selection
Sort.
6.
Loop dalam pada Inserion Sort sangat cepat, sehingga
membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang
sedikit.
7.
Stabil.
-
Kekurangan
a. Banyaknya
operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
b. Untuk larik
yang jumlahnya besar ini tidak praktis.
c. Jika list
terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan
mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
d. Membutuhkan
waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan
elemen dalam jumlah besar.
Contoh program
#include
<stdio.h>
int main()
{
int n, array[1000], c, d, t;
printf("MASUKAN BANYAK DATA : \n");
scanf("%d", &n);
printf("masukkan data 1 sampai banyak
data \n", n);
for (c = 0; c < n; c++) {
scanf("%d", &array[c]);
}
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d] <
array[d-1]) {
t
= array[d];
array[d]
= array[d-1];
array[d-1] = t;
d--;
}
}
printf("Data yang sudah terurut
:\n");
for (c = 0; c <= n - 1; c++) {
printf("%d\n", array[c]);
}
return 0;
}
Outputnya:
Tidak ada komentar:
Posting Komentar