Berikut adalah contoh implementasi algoritma insertion sort dalam bahasa pemrograman Python
Dalam contoh di atas, fungsi insertion_sort() menerima sebuah array arr sebagai input dan mengembalikan array yang telah diurutkan. Algoritma bekerja dengan memindahkan satu elemen setiap kali, sehingga pada setiap iterasi, bagian yang sudah terurut akan semakin bertambah.
Kompleksitas Waktu Algoritma Insertion Sort
Algoritma insertion sort memiliki kompleksitas waktu yang bergantung pada kondisi data
- Kasus terbaik (best case): Ketika data sudah terurut, kompleksitas waktunya adalah O(n), di mana n adalah jumlah elemen dalam data.
- Kasus rata-rata (average case): Kompleksitas waktunya adalah O(n^2).
- Kasus terburuk (worst case): Ketika data diurutkan secara terbalik, kompleksitas waktunya juga O(n^2).
Meskipun algoritma insertion sort memiliki kompleksitas waktu yang kurang efisien dibandingkan dengan algoritma pengurutan lainnya, seperti quicksort atau mergesort, namun algoritma ini cukup sederhana dan mudah diimplementasikan. Selain itu, algoritma ini dapat menjadi pilihan yang baik untuk mengurut data yang relatif kecil atau hampir terurut.
