- Dibandingkan
- Terkecil sejauh ini
- Ditukar
- Di tempatnya
Selection sort
Selection sort membangun daftar terurut dari depan. Setiap putaran memindai nilai yang belum terurut, mencatat yang terkecil, lalu menukarnya ke tempat pertama yang belum terurut. Putar pengurutan dengan kecepatan berapa pun, atau telusuri satu perbandingan setiap kali, dan amati penghitung perbandingan, penukaran, dan putaran. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Kotak-kotak menghitung perbandingan, penukaran, dan putaran. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih jumlah batang dan urutan awalnya: acak, hampir terurut, terbalik, atau dengan sedikit nilai unik. Atau ketik angka sendiri.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja.
- Amati nilai terkecil sejauh ini berubah selama pemindaian, dan penukaran yang menaruhnya di tempatnya di akhir setiap putaran.
Cara kerja selection sort
Periksa setiap nilai dalam daftar dan ingat yang terkecil. Tukar dengan nilai pertama: tempat pertama kini sudah final. Lalu lakukan hal yang sama untuk sisa daftar, mulai satu tempat lebih jauh. Setelah n − 1 putaran, semua nilai sudah di tempatnya, dan nilai terakhir otomatis berada di tempatnya.
Banyak perbandingan, sedikit penukaran
Pemindaian tidak pernah berhenti lebih awal, karena hanya setelah memeriksa semua nilai yang tersisa barulah bisa dipastikan mana yang terkecil. Jadi selection sort melakukan tepat n(n − 1)/2 perbandingan untuk n nilai, baik daftarnya terurut, terbalik, maupun acak. Sebagai gantinya, ia melakukan paling banyak n − 1 penukaran, satu per putaran. Karena itu ia pilihan yang wajar jika memindahkan nilai jauh lebih mahal daripada membandingkan dua nilai.
Pertanyaan yang sering diajukan
Bagaimana cara kerja selection sort?
Ia berulang kali memilih nilai terkecil yang belum terurut dan menukarnya ke tempat pertama yang belum terurut. Setelah putaran k, k tempat pertama berisi k nilai terkecil secara berurutan.
Berapa perbandingan dan penukaran yang dilakukan selection sort?
Selalu n(n − 1)/2 perbandingan untuk n nilai: 45 untuk 10 nilai, 780 untuk 40. Jumlah penukaran paling banyak n − 1, satu per putaran, dan lebih sedikit jika nilai terkecil sudah di tempatnya.
Mengapa daftar terurut butuh waktu selama daftar terbalik?
Karena setiap putaran harus memeriksa semua nilai yang tersisa untuk memastikan sudah menemukan yang terkecil. Tidak seperti bubble sort dan insertion sort, selection sort tidak bisa tahu dari perbandingannya bahwa daftar sudah terurut.
Apakah selection sort stabil?
Tidak dalam bentuk umumnya. Penukaran bisa membawa satu nilai melewati nilai yang sama: pada 2, 2, 1, angka 2 pertama ditukar dengan 1 dan berakhir di belakang 2 kedua. Versi yang menggeser nilai alih-alih menukarnya bersifat stabil, dengan biaya lebih banyak pemindahan.
Apakah angka saya dikirim ke suatu tempat?
Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor