Pengurutan seleksi
Mencari nilai terkecil yang tersisa dan menukarnya ke posisi berikutnya. Pertukarannya sangat sedikit, tapi jumlah perbandingannya selalu sama.
- terbaik Ω(n²)
- rata-rata Θ(n²)
- terburuk O(n²)
- memori O(1)
- tidak 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
- terkecil saat ini
- 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 terbalik. Jumlah perbandingannya tetap persis sama seperti untuk daftar lain mana pun.
Cara kerjanya
Telusuri bagian yang belum terurut dan cari nilai terkecil. Tukar nilai itu dengan nilai pertama yang belum terurut, sehingga satu nilai lagi ada di posisi akhirnya. Semua nilai yang tersisa selalu diperiksa, bahkan jika daftar sudah terurut.
Kapan ini pilihan yang tepat
Berguna jika memindahkan data itu mahal tetapi membacanya murah, karena ia menukar paling banyak sekali per posisi. Dalam kebanyakan kasus lain, pengurutan sisip adalah pilihan sederhana yang lebih baik.