Selection sort

Selection sort mengurutkan daftar seperti banyak orang mengurutkan kartu di tangan: cari yang terkecil, taruh di depan, lalu cari yang terkecil dari sisanya. Ia melakukan banyak perbandingan tetapi sangat sedikit penukaran, dan waktu jalannya hampir tidak bergantung pada urutan daftar.

Batang-batang dengan tinggi berbeda sedang diurutkan, bagian terurut di kiri, batang terkecil yang tersisa disorot, dan panah menunjukkan batang itu ditukar ke tempatnya
Batang-batang dengan tinggi berbeda sedang diurutkan, bagian terurut di kiri, batang terkecil yang tersisa disorot, dan panah menunjukkan batang itu ditukar ke tempatnya

Idenya

Bagi daftar menjadi bagian terurut di kiri, yang awalnya kosong, dan bagian belum terurut di kanan. Pindai bagian yang belum terurut dan ingat di mana nilai terkecilnya. Tukar nilai itu dengan nilai pertama yang belum terurut: bagian terurut bertambah satu. Ulangi sampai hanya tersisa satu nilai, yang pasti yang terbesar.

Contoh

Ambil 5, 1, 4, 2, 8. Putaran pertama memindai kelima nilai, menemukan 1 sebagai yang terkecil, dan menukarnya dengan 5: 1, 5, 4, 2, 8. Putaran kedua memindai 5, 4, 2, 8, menemukan 2 dan menukarnya dengan 5: 1, 2, 4, 5, 8. Putaran ketiga mendapati 4 sudah di tempatnya, dan putaran keempat mendapati 5 sudah di tempatnya, jadi tidak ada yang bergerak. Totalnya 4 + 3 + 2 + 1 = 10 perbandingan dan hanya 2 penukaran. Bubble sort butuh 4 penukaran pada daftar yang sama.

Jumlah perbandingan selalu sama

Untuk memastikan nilai mana yang terkecil, pemindaian harus memeriksa setiap nilai yang tersisa. Putaran 1 melakukan n − 1 perbandingan, putaran 2 melakukan n − 2, dan seterusnya sampai 1, yang jika dijumlahkan menjadi n(n − 1)/2. Angka ini tidak bergantung pada daftarnya: daftar terurut butuh perbandingan persis sebanyak daftar terbalik. Selection sort tidak bisa berhenti lebih awal, karena pemindaian yang menemukan nilai terkecil sudah di depan tidak mengetahui apa pun tentang sisanya.

Sedikit penukaran

Setiap putaran melakukan paling banyak satu penukaran, jadi selection sort tidak pernah melakukan lebih dari n − 1 penukaran, dan ia melewatkan penukaran jika nilai terkecil sudah di tempatnya. Bubble sort dan insertion sort melakukan penukaran sebanyak pasangan yang salah urutan, yang bisa mencapai sekitar n²/2. Jika menulis satu nilai jauh lebih mahal daripada membaca dua, misalnya pada memori yang aus setiap kali ditulisi, sedikitnya penukaran menjadi keunggulan.

Tidak stabil

Sebuah pengurutan disebut stabil jika nilai-nilai yang sama tetap dalam urutan aslinya. Selection sort tidak stabil, karena penukaran jarak jauh bisa membawa satu nilai melewati nilai yang sama. Pada 2, 2, 1, putaran pertama menukar 2 pertama dengan 1, menghasilkan 1, 2, 2 dengan kedua angka 2 kini dalam urutan terbalik. Versi yang menggeser nilai-nilai di antaranya alih-alih menukar bersifat stabil, tetapi memindahkan jauh lebih banyak nilai.

Jelajahi

Buka aplikasinya dan tekan Putar, atau tekan Langkah untuk maju satu perbandingan setiap kali. Nilai yang sedang dipindai disorot, nilai terkecil sejauh ini punya warna sendiri, dan setiap putaran diakhiri dengan penukaran ke bagian terurut di kiri. Coba daftar terurut dan daftar terbalik: jumlah perbandingannya sama, hanya penukarannya yang berbeda.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu selection sort?

O(n²) dalam semua kasus: tepat n(n − 1)/2 perbandingan untuk n nilai, apa pun urutannya. Ia melakukan paling banyak n − 1 penukaran dan hanya butuh memori tambahan O(1).

Apa bedanya selection sort dan bubble sort?

Bubble sort menukar nilai bertetangga sambil berjalan dan bisa berhenti lebih awal begitu satu putaran tidak melakukan penukaran. Selection sort hanya mengingat di mana nilai terkecil berada dan melakukan satu penukaran di akhir setiap putaran. Selection sort melakukan lebih sedikit penukaran; bubble sort lebih cepat pada daftar yang hampir terurut.

Apakah selection sort stabil?

Tidak. Penukaran bisa memindahkan satu nilai melewati nilai lain yang sama dengannya, sehingga nilai-nilai yang sama bisa berubah urutan. Ia bisa dibuat stabil dengan menggeser nilai alih-alih menukarnya, dengan biaya lebih banyak pemindahan.

Apa hubungan heap sort dengan selection sort?

Heap sort adalah selection sort dengan cara lebih cepat untuk menemukan nilai berikutnya: ia menyimpan bagian yang belum terurut dalam heap, sehingga setiap pemilihan butuh sekitar log n langkah alih-alih pemindaian penuh. Itu menurunkan totalnya menjadi O(n log n).

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba selection sort