Dalam dunia pemrograman, pengurutan data merupakan salah satu operasi dasar yang sering digunakan. Terdapat berbagai algoritma pengurutan (sorting algorithm) yang dapat digunakan, salah satunya adalah algoritma insertion sort.
Memahami Algoritma Insertion Sort
Algoritma Insertion Sort adalah salah satu algoritma pengurutan sederhana yang bekerja dengan membagi data menjadi dua bagian bagian yang sudah terurut dan bagian yang belum terurut. Algoritma ini memindahkan satu elemen dari bagian yang belum terurut ke posisi yang tepat di bagian yang sudah terurut.
Berikut adalah langkah-langkah algoritma insertion sort:
1. Mulai dengan elemen kedua dalam daftar (indeks 1).
2. Bandingkan elemen saat ini dengan elemen sebelumnya.
3. Jika elemen saat ini lebih kecil dari elemen sebelumnya, tukarkan posisinya.
4. Lanjutkan langkah 2 dan 3 hingga elemen saat ini berada pada posisi yang tepat dalam bagian yang sudah terurut.
5. Ulangi langkah 1-4 untuk setiap elemen dalam daftar.
Algoritma ini bekerja dengan memindahkan satu elemen setiap kali, sehingga pada setiap iterasi, bagian yang sudah terurut akan semakin bertambah.
Contoh Implementasi Algoritma Insertion Sort
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.
