Insertion Sort (Metode Penyisipan)

• Insertion Sort merupakan algoritma yang efisien untuk mengurutkan angka yang mempunyai jumlah elemen sedikit. Dimana:- Input : deretan angka sejumlah n buah. Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending.
• Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.
• Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secara berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.
• Insertion Sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.

• Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.
• Berikut adalah simulasi Algoritma Insertion Sort. Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.
  

Dari gambar di atas proses pengurutan / sorting  data dilakukan dengan cara memindahkan  posisi  dari satu index ke index lain dalam satu array.  

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. Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit. 

Kekurangan:

1. Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
2. Untuk larik yang jumlahnya besar ini tidak praktis.
3. Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.