pernahkah kalian mendengar atau mengetahui apa itu Insertion Sort ..??
kalau belum pernah... oke kali ini belajar bareng dengan kami, karena ilmu ini sangat penting digunakan oleh orang-orang IT, jadi kalau ingin menjadi IT profesional perlu mengetahui dan memahami ilmu sorting dalam pemrograman.
Insertion sort adalah Salah satu algoritma sorting yang paling sederhana. Insertion Sort disebut-sebut sebagai metode pertengahan. Artinya, metode ini memiliki kecepatan rata-rata antara metode primitif (bubble dan selection) dan modern (merge dan quick). Metode ini, didasarkan pada sebuah kunci yang diambil pada elemen ke-2 pada sebuah larik, lalu menyisipkan elemen tersebut jika kondisi percabangan terpenuhi. Metode penyisipan (insertion) bertujuan untuk menjadikan bagian sisi kiri larik terurutkan sampai dengan seluruh larik berhasil diurutkan.
Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu
Anggaplah bahwa terdapat sebuah meja yang berisi setumpuk kartu. Meja ini melambangkan kondisi larik sebelum diurutkan. Langkah-langkah pengurutan adalah sebagai berikut:
- Ambil kartu pertama dari meja, letakkan di tangan kiri.
- Ambil kartu kedua dari meja, bandingkan dengan kartu yang berada di tangan kiri, kemudian letakkan pada urutan yang sesuai setelah perbandingan.
- Ulangi proses hingga seluruh kartu pada meja telah diletakkan berurutan pada tangan kiri. Kartu-kartu pada tangan kiri tersebut menunjukkan kondisi larik sesudah diurutkan. Pseudocode untuk algoritma insertion sort adalah sebagai berikut:insertionsort(data[],n)
for(i = 1; i < n; i++)
pindahkan seluruh elemen
data[j] yang lebih besar
daripada data[i] sebanyak
satu posisi;
geser data[ i ] pada posisi
yang tepat
Kondisi terburuk (worst case) tercapai jika data telah urut namun dengan urutan yang terbalik. Pada kasus ini, untuk setiap i, elemen data[i] lebih kecil dari elemen data[0], …, data[i-1], masing-masing dari elemen dipindahkan satu posisi.
Untuk setiap iterasi i pada kalang for terluar, selalu ada perbandingan i, sehingga jumlah total perbandingan untuk seluruh iterasi pada kalang ini adalah:
itulah sedikit Informasi, semoga bermanfaat.
source = http://eprints.unsri.ac.id/2644/2/Jurnal_Infotel_2_-_Akatel_SP.pdf