Bucket Sorting

Bucket sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set data.

Algoritma Sorting (Bucket Sort)

Bucketsort Kode Java

Semacam ember, atau bin semacam, adalah algoritma sorting yang bekerja dengan partisi array ke sejumlah bucket. Setiap bucket kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma sorting bucket. Ini adalah semacam distribusi, dan merupakan sepupu dari radix semacam di paling untuk setidaknya rasa signifikan digit. Semacam bucket adalah generalisasi semacam mengesampingkan. Sejak semacam bucket bukanlah perbandingan semacam, yang Ω (n log n) batas bawah tidak dapat diterapkan. Perkiraan kompleksitas komputasi melibatkan jumlah ember.
Bucket semacam bekerja sebagai berikut:

1. Mengatur array awalnya kosong " bucket "

2. Scatter: Pergi array asli, menempatkan setiap objek dalam bucket nya.

3. Urutkan setiap kotak tidak kosong.

4. Kumpulkan: Kunjungi bucket dalam rangka dan menempatkan semua elemen kembali ke array asli.

Isi

    1 Pseudocode
    2 Optimasi
    3 Varian
        3.1 ember Generic semacam
        3.2 ProxmapSort
        3.3 Histogram semacam
        3,4 semacam Postman dunia
        3,5 semacam Shuffle
    4 Perbandingan dengan algoritma pengurutan lainnya
    5 Referensi
    6 Pranala luar

Pseudocode

Fungsi bucketSort (array, n) adalah
  ember ← array baru n daftar kosong
  untuk i = 0 sampai (panjang (array) -1) melakukan
    masukkan array [i] ke dalam bucket [msbits (array [i], k)]
  untuk i = 0 sampai n - 1 lakukan
    nextSort (ember [i]);
  kembali gabungan dari ember [0], ...., ember [n-1]

Berikut array array akan diurutkan dan n adalah jumlah bucket untuk digunakan. The msbits fungsi (x, k) mengembalikan k bit yang paling signifikan dari x (lantai (x / 2 ^ (ukuran (x) -k))); fungsi yang berbeda dapat digunakan untuk menerjemahkan berbagai elemen dalam array ke n bucket, seperti menerjemahkan huruf A-Z ke 0-25 atau mengembalikan karakter pertama (0-255) untuk menyortir string. Fungsi nextSort adalah fungsi pemilahan; menggunakan bucketSort dirinya sebagai nextSort menghasilkan relatif radix semacam; khususnya, kasus n = 2 sesuai dengan quicksort (meskipun berpotensi dengan pilihan poros miskin).

Optimasi

Sebuah optimasi umum adalah untuk menempatkan elemen unsorted dari bucket kembali array pertama asli, kemudian jalankan insertion sort lebih array lengkap; karena runtime insertion sort didasarkan pada seberapa jauh setiap elemen adalah dari posisi akhir, jumlah perbandingan masih relatif kecil, dan hirarki memori yang lebih baik dimanfaatkan dengan menyimpan daftar contiguously dalam memori.

Varian Generik semacam bucket

Varian yang paling umum dari bucket semacam beroperasi pada daftar n input numerik antara nol dan beberapa nilai maksimum M dan membagi rentang nilai ke n bucket masing-masing ukuran M / n. Jika setiap kotak diurutkan menggunakan insertion sort, semacam itu dapat ditunjukkan untuk berjalan dalam waktu linier diharapkan (di mana rata-rata diambil atas semua masukan mungkin) Namun, kinerja semacam ini mendegradasi dengan clustering.; jika banyak nilai-nilai terjadi berdekatan, mereka semua akan jatuh ke dalam bucket tunggal dan diurutkan secara perlahan.

Mirip dengan bucket generik semacam seperti dijelaskan di atas, ProxmapSort bekerja dengan membagi array kunci ke subarrays melalui penggunaan "peta kunci" fungsi yang melindungi sebuah memesan parsial pada tombol; karena setiap tombol ditambahkan ke subarray yang, insertion sort digunakan untuk menjaga subarray diurutkan, sehingga seluruh array yang terurut saat ProxmapSort selesai. ProxmapSort berbeda dari macam bucket dalam penggunaan kunci peta untuk menempatkan data sekitar tempatnya untuk disortir, menghasilkan "proxmap" - pemetaan kedekatan - kunci.

Histogram semacam

Varian lain dari semacam ember dikenal sebagai histogram semacam atau menghitung semacam menambahkan lulus awal yang menghitung jumlah elemen yang akan jatuh ke dalam setiap kotak menggunakan array count. Dengan menggunakan informasi ini, nilai array dapat diatur menjadi urutan ember di tempat dengan urutan pertukaran, tanpa meninggalkan overhead ruang untuk penyimpanan bucket.

Semacam tukang pos

Semacam itu Postman adalah varian dari semacam bucket yang mengambil keuntungan dari struktur hirarki elemen, biasanya dijelaskan oleh satu set atribut. Ini adalah algoritma yang digunakan oleh mesin sortasi surat-in kantor pos: mail diurutkan pertama antara domestik dan internasional; kemudian oleh negara, provinsi atau wilayah; maka dengan kantor pos tujuan; maka dengan rute, dll Sejak kunci tidak dibandingkan terhadap satu sama lain, memilah waktu O (cn), di mana c tergantung pada ukuran kunci dan jumlah ember. Hal ini mirip dengan radix semacam yang bekerja "top down", atau "yang paling digit signifikan pertama."

Semacam Shuffle

Shuffle semacam [5] adalah varian dari semacam bucket yang diawali dengan menghapus pertama 1/8 item n yang akan diurutkan, macam mereka secara rekursif, dan menempatkan mereka dalam array. Hal ini menciptakan n / 8 " bucket " yang tersisa 7/8 item didistribusikan. Setiap " bucket" kemudian disortir, dan " bucket" di rubah menjadi array diurutkan. Semacam Shuffle digunakan sebagai langkah semacam J.
Perbandingan dengan algoritma pengurutan lainnya

Bucket sort dapat dilihat sebagai generalisasi dari menghitung semacam; pada kenyataannya, jika setiap kotak memiliki ukuran 1 maka bucket semacam merosot ke menghitung semacam. Ukuran bucket variabel semacam bucket memungkinkan untuk menggunakan O (n) memori bukan O (M) memori, di mana M adalah jumlah nilai-nilai yang berbeda; dalam pertukaran, itu menyerah menghitung semacam ini O (n + M) perilaku terburuk.

Semacam bucket dengan dua bucket secara efektif versi quicksort mana nilai poros selalu dipilih untuk menjadi nilai tengah kisaran nilai. Sementara pilihan ini berlaku efektif untuk input merata, cara lain memilih pivot di quicksort seperti pivot yang dipilih secara acak membuatnya lebih tahan terhadap pengelompokan dalam distribusi input.

Algoritma mergesort n-cara juga dimulai dengan mendistribusikan daftar ke n sublists dan memilah masing-masing; Namun, sublists diciptakan oleh mergesort memiliki rentang nilai yang tumpang tindih sehingga tidak dapat digabungkan dengan Rangkaian sederhana seperti di semacam ember. Sebaliknya, mereka harus disisipkan oleh algoritma merge. Namun, biaya tambahan ini diimbangi dengan fase pencar sederhana dan kemampuan untuk memastikan bahwa setiap sublist adalah ukuran yang sama, memberikan waktu yang baik terburuk terikat.

Top-down radix sort dapat dilihat sebagai kasus khusus dari bucket semacam mana kedua rentang nilai dan jumlah ember dibatasi menjadi kekuatan dua. Akibatnya, ukuran setiap kotak adalah juga kekuatan dua, dan prosedur dapat diterapkan secara rekursif. Pendekatan ini dapat mempercepat fase pencar, karena kita hanya perlu memeriksa awalan dari representasi bit dari setiap elemen untuk menentukan ember nya.

Bucket sort, atau bisa disebut bin sort ,merupakan sebuah algoritma pengurutan yang berkerja dengan membagi setiap array ke dalam beberapa bucket (keranjang). Setiap bucket mengurutkan sendiri-sendiri array yang ada didalamnya dengan algoritma sorting yang lain atau secara rekursif menggunakan algoritma bucket sort.

Cara kerja algoritma bucket sort dapat dijelaskansebagai berikut :

-Tentukan array yang ingin diurutkan.

-Tentukan jumlah bucket dan rentang masing-masing bucket.

-Masukkan array

-array tersebut ke dalam bucket yang telah ditentukan.

-Di dalam masing-masing bucket, array tersebut di urutkan.

-Setelah itu keluarkan hasil urutan dari dalam bucket dan kembalikan ke array awal.

Bucket Sort :

 Algoritma:

• Cari nilai maksimum dan minimum di array
• Inisialisasi array bucket Daftar <> unsur (ukuran maxValue – minValue + 1)
• Pindahkan elemen dalam array untuk bucket
• Write bucket keluar (dalam rangka) ke array yang asli