Insertion Sort adalah sebuah algortima sederhana yang cukup efisien untuk mengurutkan sebuah list yang hampir terurut. Algoritma ini juga bisa digunakan sebagai bagian algoritma yang lebih canggih (Traju, 2010:3). Cara kerja algoritma ini adalah dengan mengambil elemen list satu-per-satu dan memasukkannya di posisi yang benar seperti namanya. Pada array, list yang baru dan elemen sisanya dapat berbagi tempat di array, meskipun cukup rumit. Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat. Hal ini terus dilakukan sampai tidak ada elemen tersisa di input (Traju, 2010:3).
Metode pengurutan insertion sort merupakan pengurutan data yang membandingkan dengan dua elemen data pertama, kemudian membandingkan elemenelemen data yang sudah diurutkan, kemudian perbandingan tersebut akan terus diulang hingga tidak ada elemen data yang tersisa. Metode bucket sort dengan menggunakan insertion sort. Prinsif dasar insertion adalah secara berulang –ulang menyisipkan / memasukkan setiap elemen, kedalam posisinya / tempatnya yang benar. Prinsip kerja insertion sort adalah :
Cara Kerja Algoritma Insertion Sort
- Pengecekan mulai dari data ke-1 sampai ke-n
- Bandingkan data ke-1 (1=data ke-2s/d data ke-n)
- Bandingkan data jika lebih kecil maka data ke-1 tersebut dengan data sebelumnnya (i-1), jika lebih kecil maka data trsebut dapat disisipkan kedata awal sesuai dengan posisi yang seharusnya.
Contoh: insertion sort
Data: 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
Langkah 2 : 10 22 15 3 8 2
Langkah 3 : Ulangi langkah 1 dan 2
Iterasi 2
Langkah 1 : 10 22 15 3 8 2
Langkah 2 : 10 15 22 3 8 2
Langkah 3 : Ulangi langkah 1 dan 2
Lakukan iterasi selanjutnya samapai iterasi ke-6
Setiap ada pemindahan, maka elemen yang sudah ada akan di insert sehingga akan bergeser kebelakang. Pseudocode untuk Bucket Sort dengan menggunakan bahasa pemrograman C++ adalah sebagai berikut :
Function bucketsort (array A, n) is n < -length [A]
bucket new array of n empaty list
for I = 1 to n do
insert array [i] into
buckets[n*A[i]/ max value)]
end for
for I =0 to n – 1 do
sort list buckets[i]with insertion
sort,as example
end for
concatenate list of buckets[0]
buckets[n-1] together
end function
Pembahasan lainnya :
