Insertion sort
Insertion sort adalah cara kebanyakan orang mengurutkan kartu di tangan: ambil kartu berikutnya dan selipkan ke tempat yang tepat di antara kartu yang sudah berurutan. Algoritma ini lambat pada daftar acak yang panjang, tetapi sangat cepat pada daftar pendek atau hampir terurut, karena itulah pustaka pengurutan sungguhan masih memakainya.
Idenya
Jaga bagian depan daftar tetap terurut. Di awal, bagian terurut itu hanya nilai pertama. Ambil nilai berikutnya dan bandingkan dengan nilai di depannya. Jika nilai itu lebih besar, tukar keduanya dan bandingkan lagi, satu tempat lebih mundur. Berhenti jika nilai di depannya tidak lebih besar, atau jika nilai itu mencapai posisi paling depan. Bagian terurut bertambah satu. Ulangi untuk setiap nilai sampai akhir.
Contoh
Ambil 5, 1, 4, 2, 8. Putaran 1 mengambil 1: 5 lebih besar, jadi keduanya ditukar, dan 1 mencapai posisi paling depan: 1, 5, 4, 2, 8. Putaran 2 mengambil 4: ditukar dengan 5, lalu berhenti di 1: 1, 4, 5, 2, 8. Putaran 3 mengambil 2: ditukar dengan 5 dan dengan 4, lalu berhenti di 1: 1, 2, 4, 5, 8. Putaran 4 mengambil 8, yang sudah lebih besar dari 5, jadi satu perbandingan cukup. Totalnya 7 perbandingan dan 4 penukaran. Pada daftar yang sama, bubble sort butuh 9 perbandingan, selection sort 10.
Penukaran sama dengan inversi
Inversi adalah sepasang nilai dalam urutan yang salah. Menukar dua tetangga yang salah urutan menghapus tepat satu inversi, dan insertion sort hanya menukar tetangga seperti itu. Jadi jumlah penukarannya tepat sama dengan jumlah inversi pada daftar awal, sama seperti bubble sort. Setiap putaran juga melakukan paling banyak satu perbandingan yang tidak berujung penukaran, yaitu yang menghentikannya. Jadi jumlah perbandingan adalah jumlah inversi ditambah paling banyak n − 1.
Adaptif: cepat jika daftar hampir terurut
Karena kerjanya sebanyak jumlah inversi ditambah sekitar n, insertion sort cepat setiap kali inversinya sedikit. Daftar terurut butuh n − 1 perbandingan tanpa penukaran. Daftar yang setiap nilainya hanya beberapa tempat dari posisinya butuh waktu mendekati n. Hanya daftar yang jauh dari terurut, seperti daftar terbalik dengan n(n − 1)/2 inversi, yang butuh waktu sebanding dengan n². Pada daftar acak, rata-ratanya sekitar n²/4 penukaran.
Di mana dipakai
Insertion sort stabil, tidak butuh memori tambahan, dan overhead-nya sangat kecil. Untuk daftar pendek, algoritma ini mengalahkan algoritma yang di atas kertas lebih cepat. Banyak pengurutan pustaka, seperti Timsort di Python dan Java serta introsort yang dipakai di C++, beralih ke insertion sort untuk bagian kecil daftar, biasanya sampai beberapa puluh nilai. Algoritma ini juga cocok untuk data yang datang satu per satu, karena setiap nilai baru bisa langsung disisipkan begitu tiba.
Jelajahi
Buka aplikasinya dan tekan Putar, atau tekan Langkah untuk maju satu perbandingan setiap kali. Nilai yang sedang disisipkan punya warna sendiri, nilai pembandingnya disorot, dan bagian terurut berwarna hijau. Tidak seperti bubble sort dan selection sort, bagian hijau belum final: nilai lebih kecil yang datang kemudian masih bisa bergeser masuk. Coba daftar yang hampir terurut untuk melihat betapa pendek putarannya, lalu daftar terbalik.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu insertion sort?
O(n²) pada kasus terburuk dan rata-rata, dan O(n) pada kasus terbaik, yaitu daftar yang sudah terurut. Lebih tepatnya, waktunya sebanding dengan n ditambah jumlah inversi. Memori tambahan yang dibutuhkan hanya O(1).
Apa beda insertion sort dan selection sort?
Selection sort memindai seluruh bagian yang belum terurut untuk mencari nilai terkecil, jadi selalu melakukan n(n − 1)/2 perbandingan tetapi sedikit penukaran. Insertion sort mengambil nilai berikutnya apa adanya dan memindahkannya mundur sejauh yang perlu saja, jadi perbandingannya lebih sedikit, terutama pada daftar yang hampir terurut, tetapi penukarannya lebih banyak.
Apa itu binary insertion sort?
Versi yang mencari tempat nilai baru dengan pencarian biner di bagian terurut, sehingga butuh sekitar log n perbandingan, bukan hingga n. Nilai-nilainya tetap harus digeser untuk memberi ruang, jadi jumlah perpindahan dan kasus terburuk O(n²) tetap sama.
Apakah insertion sort stabil?
Ya. Sebuah nilai hanya bergerak mundur melewati nilai yang benar-benar lebih besar, jadi nilai yang sama tetap dalam urutan aslinya.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba insertion sort