Digit dibaca
Pemindahan
Putaran

  • Ember yang dipakai
  • Baru dipindah
  • Disalin kembali
  • Di tempatnya

Info lebih lanjut tentang radix sort

Radix sort

Radix sort mengurutkan bilangan bulat tanpa pernah membandingkan dua di antaranya. Ia mengurutkan daftar berdasarkan digit satuan, lalu puluhan, lalu ratusan, setiap kali memindahkan nilai ke sepuluh ember dan menyalinnya kembali secara berurutan. Saksikan ember terisi di baris di bawah daftar, satu pemindahan setiap kali, dan lihat daftar terurut berdasarkan makin banyak digit. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu pemindahan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Ember 0 sampai 9 berjajar di baris di bawah daftar. Kotak-kotak menghitung digit yang dibaca, pemindahan, dan putaran. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri hingga 999. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Pilih jumlah batang dan urutan awalnya, atau ketik bilangan bulat sendiri hingga 999 untuk melihat putaran ratusan.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk memindahkan satu nilai setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pengurutan.
  3. Amati setiap putaran: hitung digitnya, pindahkan setiap nilai ke embernya, lalu salin ember-ember kembali.

Cara kerja radix sort

Lihat hanya digit terakhir setiap angka dan urutkan daftar berdasarkan digit itu: masukkan setiap angka ke salah satu dari sepuluh ember, 0 sampai 9, dengan menjaga urutan kedatangannya, lalu salin ember-ember itu kembali satu per satu. Lakukan hal yang sama dengan digit puluhan, lalu ratusan. Karena setiap putaran menjaga urutan angka yang digitnya sama, putaran-putaran sebelumnya tetap menentukan urutan di antara mereka, dan setelah putaran terakhir seluruh daftar terurut.

Sama sekali tanpa perbandingan

Pengurutan berbasis perbandingan butuh setidaknya sekitar n log₂ n perbandingan dalam kasus terburuk, apa pun trik cerdik yang dipakai. Radix sort menghindari batas itu dengan membaca digit: setiap putaran membaca satu digit dari setiap nilai dan memindahkan setiap nilai dua kali, jadi d digit butuh d putaran dan kerjanya tumbuh sebanding n · d. Untuk daftar panjang berisi kunci pendek, ini menguntungkan: satu juta angka hingga 999 cukup tiga putaran, sedangkan pengurutan berbasis perbandingan butuh sekitar 20 juta perbandingan. Harganya, ia hanya berlaku untuk kunci yang terdiri dari digit atau karakter, dan butuh ruang untuk ember.

Pertanyaan yang sering diajukan

Bagaimana cara kerja radix sort?

Ia mengurutkan angka berdasarkan digit terakhirnya, lalu digit sebelumnya, dan seterusnya hingga digit pertama. Setiap putaran memasukkan angka ke sepuluh ember berdasarkan digit itu, dengan menjaga urutannya, lalu menyalin ember kembali. Setelah putaran untuk digit paling signifikan, daftar sudah terurut.

Mengapa mulai dari digit terakhir?

Karena setiap putaran stabil: angka dengan digit yang sama mempertahankan urutan dari putaran sebelumnya. Jadi putaran terakhir, pada digit pertama, menentukan urutan, dan angka yang seri diurutkan oleh digit yang sudah terurut. Ini disebut LSD (least significant digit) radix sort.

Apakah radix sort lebih cepat daripada quicksort?

Bisa, untuk banyak kunci pendek: kerjanya tumbuh sebanding jumlah nilai dikali jumlah digit, tanpa n log n. Untuk sedikit nilai, kunci yang sangat panjang, atau data yang tidak terdiri dari digit, quicksort dan merge sort biasanya lebih cepat dan lebih sederhana.

Apa hubungannya dengan counting sort?

Setiap putaran radix sort adalah counting sort pada satu digit: hitung berapa nilai yang memiliki tiap digit, tentukan di mana tiap ember mulai, lalu pindahkan nilai ke sana secara berurutan.

Apakah angka saya dikirim ke mana pun?

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