- Dibandingkan
- Ditandai (terkecil, pivot, atau kunci)
- Ditukar atau dipindah
- Di tempatnya
| Peringkat | Algoritma | Perbandingan atau pembacaan | Penukaran atau pemindahan | Operasi |
|---|
Adu pengurutan
Algoritma pengurutan mana yang tercepat? Tergantung daftarnya. Adu pengurutan menjalankan kedelapan algoritma pengurutan pada daftar yang sama sekaligus, masing-masing di satu lintasan, dan menghitung setiap perbandingan, pembacaan, penukaran, dan pemindahan sebagai satu operasi. Lintasan maju seiring hitungannya bertambah, jadi Anda bisa melihat pengurutan yang efisien selesai sementara yang lambat masih menukar, dan melihat peringkatnya berubah saat daftar hampir terurut atau terbalik. Tekan Putar untuk melihat kedelapan algoritma pengurutan berlomba pada daftar yang sama, atau Langkah dan Mundur untuk maju satu operasi setiap kali. Geser penggeser untuk melompat ke mana saja. Setiap perbandingan, pembacaan, penukaran, atau pemindahan dihitung satu operasi, dan setiap lintasan maju seiring hitungannya sendiri bertambah, jadi pengurutan yang butuh operasi paling sedikit selesai lebih dulu. Pilih jumlah batang dan 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 dan amati kedelapan lintasan. Langkah dan Mundur maju satu operasi setiap kali; penggeser melompat ke mana saja dalam balapan.
- Bandingkan tabel hasil, lalu coba daftar yang hampir terurut dan yang terbalik untuk melihat peringkatnya berubah.
Cara kerja balapan
Kedelapan pengurutan mendapat daftar yang sama. Setiap perbandingan dua nilai, setiap digit atau nilai yang dibaca radix sort dan counting sort, dan setiap penukaran atau pemindahan dihitung satu operasi. Pada setiap saat dalam balapan, setiap lintasan menunjukkan sejauh mana pengurutannya sudah berjalan dengan operasi sebanyak itu. Pengurutan yang butuh lebih sedikit operasi lebih cepat mencapai akhir. Tabel hasil mencantumkan perbandingan, penukaran atau pemindahan, dan totalnya untuk setiap pengurutan.
Apa yang ditunjukkan hasilnya
Pada 40 nilai acak, counting sort butuh sekitar 120 operasi, radix sort sekitar 240, quicksort sekitar 260, dan merge sort sekitar 380. Heap sort menyusul dengan sekitar 490, sedangkan selection sort dan insertion sort butuh sekitar 820 dan bubble sort lebih dari 1.100. Pada daftar yang hampir terurut, insertion sort menang dengan sekitar 50, dan bubble sort kedua. Pada daftar terbalik, bubble sort dan insertion sort sama-sama butuh 1.560. Counting sort dan radix sort sering menang karena nilai-nilai ini bilangan bulat kecil; pada data lain keduanya sama sekali tidak bisa dipakai.
Pertanyaan yang sering diajukan
Algoritma pengurutan mana yang tercepat?
Tergantung datanya. Untuk bilangan bulat kecil, counting sort dan radix sort butuh operasi paling sedikit. Untuk data umum, quicksort dan merge sort tercepat pada daftar acak, dan insertion sort tercepat pada daftar yang hampir terurut. Bubble sort dan selection sort lambat kecuali pada daftar yang sangat kecil.
Apa yang dihitung sebagai operasi?
Setiap perbandingan dua nilai, setiap digit atau nilai yang dibaca radix sort dan counting sort, dan setiap penukaran atau pemindahan suatu nilai. Ini model sederhana: waktu berjalan sebenarnya juga bergantung pada akses memori dan biaya setiap operasi.
Mengapa counting sort dan radix sort begitu sering menang?
Karena keduanya tidak pernah membandingkan nilai. Keduanya memanfaatkan fakta bahwa nilainya bilangan bulat kecil, sehingga kerjanya tumbuh sebanding dengan n ditambah rentang nilai, bukan dengan n log n. Pada data yang bukan bilangan bulat kecil, keduanya tidak berlaku.
Mengapa insertion sort menang pada daftar yang hampir terurut?
Karena kerjanya sama dengan jumlah nilai ditambah jumlah pasangan yang salah urutan. Daftar yang hampir terurut hanya punya sedikit pasangan seperti itu, jadi setiap nilai hanya bergeser satu atau dua tempat.
Apakah angka saya dikirim ke mana pun?
Tidak. Balapan berjalan di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor