Algoritma Sorting - Insertion Sort

Image by OpenClipart-Vectors from Pixabay

Insertion sort merupakan algoritma pengurutan O(n2) yang memindahkan elemen satu per satu ke posisi yang benar. Algoritma berkerja dengan memasukkan satu elemen pada satu waktu ke bagian array yang diurutkan sebelumnya, memindahkan elemen dengan peringkat yang lebih tinggi ke atas sesuai kebutuhan. Awal mulai, elemen pertama (atau terkecil, atau sembarang) dari array yang tidak diurutkan dianggap sebagai bagian yang diurutkan.

Meskipun Insertion Sort adalah algoritma O(n2), kesederhanaannya, overhead rendah, lokalitas referensi yang baik, dan efisiensinya menjadikannya pilihan yang baik dalam dua kasus:

1. Ukuran array kecil,
2. Sebagai algoritma penyelesaian akhir untuk algoritma O (n logn) seperti mergesort dan quicksort.

Contoh proses

• 12, 11, 13, 5, 6

Contoh iterasikan i = 1 (elemen kedua pada array) hingga index 4 (elemen terakhir pada array) i = 1. Karena 11 lebih kecil banding 12, maka masukan 11 dan geser posisi 12.

• 11, 12, 13, 5, 6

i = 2. 13 akan berada tetap pada posisinya, karena 13 lebih besar dari semua elemen array sebelumnya (11 dan 12).

• 11, 12, 13, 5, 6

i = 3. 5 akan di pindah ke posisi paling awal, dan semua elemen sisahnya akan di geser 1x dari posisinya sekarang.

• 5, 11, 12, 13, 6

i = 4. 6 akan dipindah ke posisi setelah 5, dan elemen sisahnya dari 11 hingga 13 akan di geser 1x dari posisinya sekarang.

• 5, 6, 11, 12, 13

Referensi: https://www.geeksforgeeks.org/insertion-sort/

Berikut implementasi algoritma Insertion Sort di beberapa bahasa pemrograman

Link github https://github.com/madeyoga/SortingAlgorithms

Semoga bermanfaat 🙏