Pengurutan sisip
Membangun bagian terurut di kiri, satu nilai demi satu nilai. Tiap nilai baru diambil keluar lalu digeser ke kiri sampai bertemu nilai yang lebih kecil.
- terbaik Ω(n)
- rata-rata Θ(n²)
- terburuk O(n²)
- memori O(1)
- stabil
- tanpa memori tambahan
Apa artinya?
- Kasus terbaik: bagaimana waktu tumbuh seiring ukuran daftar n saat input paling mudah bagi algoritma ini.
- Rata-rata: pertumbuhan waktu biasa terhadap n. Pada n², jumlah nilai 2 kali lipat butuh sekitar 4 kali waktu; n log n jauh lebih lambat.
- Kasus terburuk: pertumbuhan pada input tersulit. Berguna saat kecepatan tidak boleh turun.
- Memori: berapa memori tambahan yang dibutuhkan selain daftar. 1 berarti beberapa variabel, n berarti salinan daftar.
- Stabil: dua nilai yang sama tetap dalam urutan aslinya. Penting saat mengurutkan data menurut satu kolom.
- Tanpa memori tambahan: mengurutkan di dalam daftar itu sendiri, tanpa daftar kedua.
- dibandingkan
- dipindahkan
- dikeluarkan
- bagian terurut
- di posisi akhir
Tekan putar: garis menunjukkan pertumbuhan biaya selama pengurutan
Tekan putar atau jalankan langkah demi langkah.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih daftar yang hampir terurut. Hampir tidak ada yang bergeser, jadi selesai dalam sedikit langkah.
Cara kerjanya
Bagian kiri selalu terurut. Ambil nilai berikutnya, geser setiap nilai yang lebih besar di bagian terurut satu posisi ke kanan, lalu masukkan nilai itu ke celah. Begitulah banyak orang mengurutkan kartu remi di tangan.
Kapan ini pilihan yang tepat
Pilihan bagus untuk daftar pendek dan daftar yang hampir terurut, karena di situ ia sangat cepat. Pustaka pengurutan sungguhan memakainya untuk potongan kecil daftar di dalam metode yang lebih cepat.