Ide Dasar
Radixsort dikembangkan berdasarkan penyortiran bucket, dan kedua penyortiran merupakan implementasi lanjutan dari mengalokasikan penyortiran. Ide dasar distributifort: proses penyortiran tidak memerlukan membandingkan kata kunci, tetapi mengimplementasikan pemilahan melalui proses "distribusi" dan "mengumpulkan". Kompleksitas waktu mereka dapat mencapai urutan linier: O (n).
Penyortiran kardinalitas adalah algoritma penyortiran yang stabil, tetapi memiliki keterbatasan tertentu:
1. Kata kunci dapat diuraikan.
2. Jumlah kata kunci yang direkam lebih kecil, dan lebih baik jika mereka padat. 3. Jika itu adalah angka, yang terbaik adalah tidak ditandatangani, jika tidak, kompleksitas pemetaan yang sesuai akan ditingkatkan. Anda pertama -tama dapat mengurutkannya secara terpisah.
Mari kita lihat penyortiran ember (Radixsort).
Penyortiran bucket juga disebut Box Sorting (BINSORT). Ide dasarnya adalah untuk mengatur beberapa ember, memindai catatan yang akan diurutkan R [0], R [1], ..., R [N-1], memuat semua catatan dengan kata kunci dalam kisaran tertentu ke dalam ember KTH (dialokasikan), dan kemudian menghubungkan kepala dan ekor dari masing-masing bucket yang tidak kosong secara berurutan (mengumpulkan) sesuai dengan nomor sequence.
Misalnya, untuk mengurutkan 52 kartu bermain yang dikocok dengan poin A <2 <... <J <q <k, 13 "ember" perlu ditetapkan. Saat menyortir, setiap kartu ditempatkan di ember yang sesuai dengan titik, dan kemudian ember terhubung secara berurutan untuk mengatur setumpuk kartu yang disusun dalam urutan titik tambahan.
Dalam penyortiran ember, jumlah ember tergantung pada kisaran nilai kata kunci. Oleh karena itu, penyortiran bucket mensyaratkan bahwa jenis kata kunci terbatas, jika tidak diperlukan ember tanpa batas mungkin.
Secara umum, tidak dapat diprediksi berapa banyak catatan dengan kata kunci yang sama disimpan di setiap ember, sehingga jenis ember harus dirancang sebagai daftar yang ditautkan.
Untuk memastikan bahwa penyortiran stabil, koneksi selama proses pengemasan dan pengumpulan harus dilakukan sesuai dengan prinsip pertama-out pertama.
Untuk penyortiran ember, waktu proses alokasi adalah O (n); Waktu proses pengumpulan adalah O (m) (daftar tertaut digunakan untuk menyimpan input yang akan diurutkan catatan) atau O (m+n). Oleh karena itu, waktu untuk penyortiran ember adalah O (M+N). Jika urutan besarnya jumlah ember m adalah O (n), waktu penyortiran ember adalah linier, yaitu, O (n).
Sebagian besar kompleksitas waktu dari algoritma penyortiran utama yang disebutkan di atas adalah O (N2), dan beberapa algoritma penyortiran adalah O (nlogn). Tetapi penyortiran barel dapat mencapai kompleksitas waktu O (n). Namun, kelemahan penyortiran ember adalah: Pertama -tama, kompleksitas ruang relatif tinggi dan overhead tambahan diperlukan. Penyortiran memiliki dua array di atas kepala, satu menyimpan array yang akan diurutkan, dan yang lainnya adalah apa yang disebut ember. Misalnya, nilai yang akan diurutkan adalah dari 0 ke M-1, maka m-muel diperlukan, dan array ember ini membutuhkan setidaknya ruang M. Kedua, elemen yang akan diurutkan harus berada dalam kisaran tertentu, dll.
Penyortiran kardinalitas adalah peningkatan penyortiran bucket, yang membuat "penyortiran ember" cocok untuk set nilai elemen yang lebih besar daripada meningkatkan kinerja.
Mari kita gunakan contoh kartu bermain untuk diilustrasikan. Kartu terdiri dari dua kata kunci: setelan (peach <heart <mei <square) + nilai nominal (a <2 <3 <4 <... <k). Jika ukuran kartu ditentukan oleh gugatan terlebih dahulu, dan kartu dengan gugatan yang sama ditentukan oleh nomor tersebut. Kami memiliki dua algoritma untuk menyelesaikan masalah ini.
Artinya, jika setelannya berbeda, tidak peduli berapa nilai nominal, kartu dengan warna setelan yang lebih rendah lebih kecil dari warna setelan dengan warna setelan yang lebih tinggi. Hanya dalam warna setelan yang sama, hubungan ukuran ditentukan oleh ukuran nilai nominal. Ini adalah pemesanan beberapa kode kunci.
Untuk mendapatkan hasil penyortiran, kami membahas dua metode penyortiran.
Metode 1: Pertama -tama mengurutkan jas dan warna dan membaginya menjadi 4 kelompok, yaitu kelompok bunga prem, kelompok persegi, kelompok jantung merah, dan kelompok jantung hitam. Kemudian urutkan setiap kelompok berdasarkan nilai nominal, dan akhirnya, hubungkan 4 kelompok bersama -sama.
Metode 2: Pertama, berikan 13 kelompok angka (No. 2, 3, ..., a) menurut 13 nilai wajah, masukkan kartu ke dalam kelompok angka yang sesuai dengan nilai -nilai wajah, dan bagikan menjadi 13 tumpukan. Kemudian, berikan 4 kelompok penomoran (bunga prem, kotak, hati merah, hati hitam), keluarkan kartu di kelompok 2 dan masukkan ke dalam kelompok warna yang sesuai, dan kemudian keluarkan kartu di grup 3 dan masukkan ke dalam kelompok warna yang sesuai, ... dengan cara ini, semua kelompok warna diperintahkan sesuai dengan nilai wajah, dan kemudian, menghubungkan 4 kelompok warna dengan urutan.
Penyortiran kode multi-kunci diurutkan secara berurutan dari kode kunci utama ke kode kunci kedua atau dari kunci kedua ke kode kunci utama, dan dibagi menjadi dua metode:
Metode prioritas bit paling signifikan (paling tidak signifikanDigitFirst), disebut sebagai metode MSD:
1) Menyortir dan mengelompokkannya dengan K1, bagilah urutan menjadi beberapa setelah. Dalam catatan kelompok sekuens yang sama, kode kunci K1 sama.
2) Kemudian urutkan setiap kelompok menjadi subkelompok dengan K2. Setelah itu, terus mengurutkan kode kunci berikut dengan cara ini sampai setiap subkelompok diurutkan berdasarkan kode kunci sekunder KD.
3) Kemudian hubungkan grup untuk mendapatkan urutan yang dipesan. Metode yang diperkenalkan dalam kartu penyortiran dengan jas dan nilai wajah adalah metode MSD.
Metode yang paling tidak signifikan, yang disebut sebagai metode LSD:
1) Mulailah menyortir dari KD, lalu urutkan KD-1, berulang secara bergantian sampai dibagi menjadi sesaat terkecil menurut K1.
2) Akhirnya, hubungkan setiap sub-urutan untuk mendapatkan urutan yang dipesan. Metode kedua yang diperkenalkan dalam penyortiran kartu berdasarkan jas dan nilai nominal adalah metode LSD.
Kata kunci tunggal dari tipe numerik atau karakter dapat dianggap sebagai kata kunci multi-kunci yang terdiri dari beberapa digit atau beberapa karakter. Pada saat ini, metode "pengumpulan alokasi" dapat digunakan untuk mengurutkannya. Proses ini disebut metode penyortiran kardinalitas, di mana jumlah nilai yang mungkin untuk setiap angka atau karakter disebut kardinalitas. Misalnya, dasar setelan kartu bermain adalah 4 dan basis nilai nominal adalah 13. Saat memilah kartu bermain, Anda dapat mengaturnya dengan gaya terlebih dahulu atau dengan nilai nominal terlebih dahulu. Saat menyortir sesuai dengan warna, pertama -tama bagilah menjadi 4 tumpukan (distribusi) dalam urutan merah, hitam, persegi dan bunga, kemudian menumpuknya bersama -sama (mengumpulkan) dalam urutan ini, dan kemudian membaginya menjadi 13 tumpukan (distribusi) dalam urutan nilai nominal, dan kemudian menumpuknya bersama -sama (mengumpulkan) dalam urutan ini. Dengan cara ini, alokasi dan koleksi sekunder dapat mengatur kartu bermain secara tertib.
Selama proses "pengumpulan alokasi", stabilitas penyortiran perlu dipastikan.
Gagasan penyortiran kardinalitas adalah untuk membuat setiap kelompok kata kunci dalam data yang akan diurutkan secara berurutan. Misalnya, urutan berikut untuk disortir:
135, 242, 192, 93, 345, 11, 24, 19
Kami membagi satu, sepuluh dan ratusan digit masing -masing nilai menjadi tiga kata kunci, misalnya:
135-> K1 (satu digit) = 5, K2 (sepuluh digit) = 3, k3 (seratus digit) = 1.
Kemudian mulailah dari bit tunggal terendah (mulai dari kata kunci terakhir), semua kata kunci K1 dari semua data dialokasikan bucket (karena, setiap angka adalah 0-9, sehingga ukuran bucket adalah 10), dan kemudian output data dalam ember secara berurutan untuk mendapatkan urutan berikut.
(11), (242, 192), (93), (24), (135, 345), (19) (menyortir mulai dari kata kunci terbanyak, mengabaikan seratus dua digit, dan dialokasikan sesuai dengan angka pada satu digit)
Kemudian urutan di atas dialokasikan untuk K2, dan urutan output adalah:
(11, 19), (24), (135), (242, 345), (192, 93) (lihat kata kunci terbanyak untuk mengurutkan kata kunci kedua, abaikan digit seratus dan tunggal, dan alokasikan sesuai dengan angka pada sepuluh digit)
Akhirnya, untuk alokasi ember K3, urutan outputnya adalah:
(011, 019, 024, 093), (135, 192), (242), (345) (lihat kata kunci kedua untuk mengurutkan kata kunci tertinggi, abaikan sepuluh dan satu digit, dan alokasikan mereka sesuai dengan angka pada seratus digit)
Penyortiran selesai.
Implementasi Java
public void radixsort () {int max = array [0]; untuk (int i = 0; i <array.length; i ++) {// Temukan nilai maksimum dalam array if (array [i]> max) {max = array [i]; }} int keysnum = 0; // Jumlah kata kunci, kami menggunakan satu digit, sepuluh digit, dan ratusan ... sebagai kata kunci, sehingga jumlah kata kunci adalah digit maksimum sementara (maks> 0) {max /= 10; keysnum ++; } Daftar <arraylist <integer>> buckets = new arraylist <arraylist <integer>> (); untuk (int i = 0; i <10; i ++) {// Nomor yang mungkin untuk setiap digit adalah 0 ~ 9, jadi atur 10 bucket ember.add (new ArrayList <Integer> ()); // Bucket terdiri dari ArrayList <Integer>} untuk (int i = 0; i <keysnum; i ++) {// Mulailah dengan kata kunci terbaru, tetapkan sesuai dengan kata kunci pada gilirannya (int j = 0; j <array.length; j ++) {// scan semua unsur array dan dugaan ke eLEMENTIONS ke The Corresing. elemen, seperti 258. Sekarang Anda perlu mengambil angka pada sepuluh digit, 258%100 = 58,58/10 = 5 int key = array [j]%(int) math.pow (10, i+1)/(int) math.pow (10, i); buckets.get (key) .add (array [j]); // Masukkan elemen ini ke dalam ember dengan kunci kata kunci} // Setelah dialokasikan, salin elemen di bucket kembali ke array int counter = 0; // penghitung elemen untuk (int j = 0; j <10; j ++) {arraylist <integer> bucket = buckets.get (j); // bucket dengan kata kunci j while (bucket.size ()> 0) {array [counter ++] = bucket.remove (0); // Salin elemen pertama dalam ember ke array dan hapus}} System.out.print ("Thread"+(i+1)+"Sort:"); menampilkan(); }}Hasil pencetakan adalah sebagai berikut:
Analisis Algoritma
Sekilas, efisiensi eksekusi jenis kardinalitas tampaknya baik dan sulit dipercaya bahwa yang harus Anda lakukan adalah menyalin item data asli dari array ke daftar yang ditautkan dan kemudian menyalinnya kembali. Jika ada 10 item data, ada 20 replikasi, ulangi proses untuk setiap bit. Dengan asumsi bahwa angka 5 digit diurutkan, 20*5 = 100 salinan diperlukan. Jika ada 100 item data, maka ada 200*5 = 1000 eksemplar. Jumlah salinan sebanding dengan jumlah item data, yaitu, O (n). Ini adalah algoritma penyortiran paling efisien yang pernah kami lihat.
Sayangnya, semakin banyak item data, kata kunci yang lebih panjang diperlukan. Jika item data meningkat 10 kali, kata kunci harus ditambahkan oleh satu (satu putaran penyortiran lagi). Jumlah salinan dan jumlah item data sebanding dengan panjang kata kunci, dan dapat dipertimbangkan bahwa panjang kata kunci adalah logaritma N. Oleh karena itu, dalam kebanyakan kasus, efisiensi eksekusi penyortiran kardinal dibalik menjadi O (N*logn), yang hampir sama dengan penyortiran cepat.
Meringkaskan
Di atas adalah seluruh konten artikel ini tentang pengantar penyortiran kardinalitas dan implementasi bahasa Java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya.