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.

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

Berikut implementasi algoritma Insertion Sort di beberapa bahasa pemrograman

Link github https://github.com/nano-devs/SortingAlgorithms

Semoga bermanfaat 🙏