28
2.7.2
Insertion Sort
Insertion
sort
adalah algoritm
sorting
yang
menyediakan satu
tempat kosong.
Sorting
jenis
ini
kurang
efisien
pada
list
dengan
jumlah
bilangan
atau
karakter
dalam
jumlah
besar
dibandingkan dengan
algoritma
yang
lebih
maju
seperti
heap
sort, quick sort, atau merge sort. Tapi insertion sort memiliki kelebihannya sendiri:
•
Mudah diimplementasikan.
•
Efisien terhadap jumlah data yang sedikit.
•
Efisien terhadap data yang sebagian sudah terurut.
•
Lebih
efisien
dalam
latihan
daripada
algoritma
lainseperti
selection
atau bubble sort.
•
Stabil
(Tidak
mengubah
urutan
relatif
elemen-elemen
dengan
nilai
sama).
•
In-place (hanya membutuhkan satu tempat kosong dalam memory).
•
Merupakan
algoritma
online,
dapat
langsung
dilakukan
sorting
pada
saat list diterima.
Algoritma Insertion sort:
1.
Array
dari
nilai-nilai
yang akan diurutkan dibagi
menjadi 2
bagian
:
bagian yang sudah terurut dan yang belum terurut.
2.
Pada
setiap
iterasi,
elemen
pertama
pada
bagian
yang
belum
terurut
diambil
dan
ditaruh
pada
posisi
yang
benar
dari
bagian
yang
sudah
terurut.
3.
Proses
sorting berlangsung
hingga elemen-elemen dalam bagian
yang
belum terurut habis.
 |