Pengertian
Insertion sort merupakan salah satu dari enam jenis metode pengurutan atau penyusunan data pada sort. Sesuai dengan namanya, metode insertion merupakan metode yang menggunakan teknik peyisipan data pada suatu kumpulan atau baris atau susunan data dalam himpunan. Data yang di-insert akan disisipkan pada baris yang sudah dibandingkan sebelumnya. Agar lebih jelas bisa kalian simak lebih lanjut di bagian metode nanti.
Pada metode insertion sort nanti akan adalah fully sorted atau penyusunan sudah full. Maksudnya? Jadi ketika suatu himpunan sudah tersusun atau sodah tersorri maka kita sebit fully sorted. Penyusunan yang sudah pas. Istilah tersebut akan digunakan pada metode sort dan salah satunya pada insertion sort. Bagaimanakah langkah penyusunan atau pengurutan data berdasarkan metode insertion sort? Dapat kita simak pada bagian pembahasan metode dibawah ini.
Metode
Metode Insertion sort akan dibahas menggunakan cara berikut. Sebelumnya kita sudah mempunyai suatu baris data yang akan kita susun. Sebagai contonya:
5 6 2 9 8 3
Dari baris diatas kita akan susun menggunakan metode insertion sort dan akan kita lakukkan secara ascending. Langkah-langkahnya adalah sebagai berikut.
1. Dari baris kita akan tetapkan nilai pada bagian paling kiri sebagai fully sorted. Pada baris bernilai 5. Maka kita tetapkan nilai 5 fully sorted.
5 6 2 9 8 3
2. Setelah itu, kita akan membandingkan kembali nilai berikutnya yaitu data yang bernilai 6. Kita bandingkan dengan nilai yang sudah fully sorted tadi yaitu 5. Setelah kita bandingkan ternyata nilai 6 lebih besar dari nilai 5. Maka tidak ada perubahan posisi alias tetap dan nilai 5 dan 6 kita nyatakan fully sorted.
5 6 2 9 8 3
3. Kembali kita bandingkan data berikutnya yaitu data bernilai 2 dengan kirinya yaitu nilai 6. Angka 2 lebih kecil dari angka 6 maka kita tukarkan posisinya.
5 2 6 9 8 3
Lalu kita bandingkan kembali dengan nilai kirinya yaitu nilai 5. Dan tetap angka 2 lebih kecil dari angka 5 sehingga kita tukarkan kembali posisinya hingga tidak ada nilai yang bisa dibandingkan. Maka nilai 2, 5, dan 6 kita nyatakan fully sorted.
2 5 6 9 8 3
4. Langkah berikutnya juga sama, kita bandingkan nilai 9 dengan kirinya yaitu angka 6. 9 Lebih besar daripada 6 maka tidak ada perubahan posisi.
5. Lalu bandingkan angka 8 dengan 9. 8 lebih kecil dari nilai 9 maka kita tukarkan posisinya.
2 5 6 8 9 3
Karena 8 lebih besar daripada 6 maka nilai 8 tidak akan kita ubah kembali posisinya sehingga nilai sudah fully sorted.
6. Kita bandingkan angka terakhir yaitu nilai 3 dengan kirinya yaitu 9. Ternyata lebih kecil, maka kita tukarkan posisinya.
2 5 6 8 3 9
Nilai 3 lebih kecil dari nilai 8 maka kita kembali tukar posisinya.
2 5 6 3 8 9
Nilai 3 lebih kecil dari nilai 6 maka kita kembali tukar posisinya.
2 5 3 6 8 9
Nilai 3 lebih kecil dari nilai 5 maka kita kembali tukar posisinya.
2 3 5 6 8 9
Karena 3 lebih besar dari nilai 2 maka penukaran posisi kita hentikan. Setelah tidak ada lagi nilai yang akan dibandingkan maka kita nyatakan baris sudah fully sorted. Baris sudah dinyatakan tersusun sepenuhnya secara ascending.
Proses yang terjadi pada pengurutan dengan menggunakan metodeInsertion Sort adalah dimulai dari data ke-2 kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama diandaikan memang sudah pada tempatnya. Ilustrasinya mirip seperti saat menyisipkan kartu di permainan kartu. Agar lebih mudah dalam memahaminya silahkan perhatikan ilustrasi gambar berikut ini:
Gambar diatas dipahami aja satu satu proses jalannya, sekarang lita lihat source code untuk insertion sort menggunakan C.
for (i = 1 ; i <= n - 1; i++)
{
j = i;
while ( j > 0 && data[j] < data[j-1])
{
temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
j--;
}
}
SUMBER : herlawati.com dan otatechnime.blogspot.co.id
