Dalam jenis distribusi, elemen didistribusikan dan didistribusikan ke dalam kelas sampai array diurutkan.
Dalam kasus yang paling umum, ini terjadi kira-kira dengan cara yang sama. Elemen-elemen disebarkan oleh kelas berdasarkan beberapa kriteria. Jika ini tidak mengarah pada pengurutan array, maka atribut dari kelas disempurnakan dan elemen-elemen tersebut tersebar lagi ke kelas yang disempurnakan. Dan ini terjadi sampai array dipesan.
Dalam menyortir berdasarkan distribusi, hampir selalu tidak ada perbandingan elemen di antara mereka dan pertukaran mereka. Yang utama adalah apakah elemen itu milik kelas tertentu atau tidak, perbandingannya dengan elemen lain jarang memainkan peran.
Biasanya, jenis ini memiliki kompleksitas waktu linier (daripada logaritmik, seperti jenis pertukaran, penggabungan, pilihan, atau sisipan yang efisien). Algoritme kelas ini hampir selalu membutuhkan banyak memori tambahan, karena elemen yang dikelompokkan berdasarkan kelas harus disimpan di suatu tempat.
Jenis distribusi bagus untuk menyortir bilangan bulat dan string. Menyortir bilangan real dengan mereka biasanya tidak nyaman. Juga, distribusi menyortir array dengan sempurna yang terdiri dari angka berulang - semakin banyak pengulangan, semakin sedikit kelas yang berbeda yang diperlukan.
Artikel ini ditulis dengan dukungan EDISON.
Opini Pelanggan: 10 plus programmer dari EDISON
Ini menarik dan bermanfaat untuk diketahui: Programmer sarapan
Pertimbangkan algoritma yang paling menunjukkan sifat cembung di atas.
Sortir ember: Sortir ember
Nama lain adalah penyortiran keranjang, penyortiran blok, penyortiran saku.
Kami menyebarkan angka dalam keranjang, lalu di setiap keranjang kami menyebar di keranjang yang lebih kecil, dan seterusnya, sampai pada tingkat tertentu dalam keranjang hanya ada elemen yang sama. Kemudian dari keranjang seperti itu dari tingkat terendah, mudah untuk mengembalikan array dalam keadaan teratur.
Mari kita jelaskan dengan contoh spesifik. Katakanlah kita memiliki array yang tidak terurut. Diketahui bahwa array ini berisi angka dari 1 hingga 8.
Kami membuang angka-angka ini ke dalam 2 kelompok: angka dari 1 hingga 4 jatuh ke dalam satu kelompok, dari 5 hingga 8 menjadi yang kedua.Kemudian kami mendistribusikan angka-angka dalam keranjang pertama menjadi dua keranjang: dalam satu angka 1 dan 2, dan yang lainnya 3 dan 4. Kami juga mendistribusikan keranjang ini ke keranjang kulit pohon, yang sudah berisi angka dengan ukuran yang sama. Untuk keranjang besar yang berisi angka dari 5 hingga 8, kami menerapkan rekursi serupa.
Kemudian, dari keranjang kecil, yang masing-masing berisi angka yang sama, kami mengembalikan elemen ke array utama dalam urutan prioritas.
Penyortiran nuklir dalam bentuk ini tidak secara khusus dapat diterapkan dalam praktik, tetapi secara standar menunjukkan bagaimana semua penyortiran menurut distribusi bekerja secara umum.
Urutkan Thanos :: Urusan Thanos
Kadang-kadang penulis macam dikirim kepada saya dan ini adalah kasus seperti itu. Penulis Andrei Danilin menyebutnya "Rusia menyortir menjadi dua," namun saya menyebutnya penyortiran Thanos. Atau, jika kita secara formal melanjutkan dari metode yang digunakan, kita dapat memanggil penyortiran rata-rata aritmatika.
Mean aritmatika elemen dihitung dalam array dan kemudian semua elemen didistribusikan ke dalam 2 kelompok. Dalam satu kelompok terdapat unsur-unsur yang lebih kecil (atau sama) dengan rata-rata aritmatika, dalam kelompok kedua - unsur-unsur lebih besar dari rata-rata aritmatika. Kemudian tindakan yang sama diterapkan secara rekursif untuk kedua kelompok - dan seterusnya hingga akhir yang pahit.
Dan bagaimana dengan titanium gila? Jika ini adalah array acak, maka pada umumnya elemen, jika dibandingkan dengan rata-rata aritmatika, memiliki kemungkinan 50/50 bahwa ia akan menuju ke salah satu dari dua grup.
Ngomong-ngomong, di internet saya menemukan algoritma komik lain dengan nama yang sama. Jika array tidak diurutkan, maka klik Infinity Glove dan kirim setengah dari elemen array yang dipilih secara acak ke tidak ada. Jika para penyintas membentuk susunan tertib, maka misi besar mereka dapat dianggap terpenuhi. Jika belum, maka Anda dapat membuat beberapa klik lagi.
Tetapi kembali ke penyortiran distribusi kami. Semuanya hanya dapat dibagi menjadi dua kelompok -
penghitungan jenis dan
penyortiran bitwise . Nah, jika Anda mau, Anda juga bisa menyoroti
penyortiran penghitungan-bit , mis. mereka yang dapat dikaitkan dengan keduanya.
Ada juga algoritma hibrid (yang menggunakan metode kelas yang berbeda, misalnya, pengurutan Tim adalah persilangan antara pengurutan gabungan dan pengurutan penyisipan, pengurutan introspektif adalah pengurutan cepat yang masuk ke pengelompokan banyak, dll.), Termasuk pengurutan distribusi Namun, hibrida adalah bagian terpisah. Tentang mereka nanti.
Ribuan penyortiran dan aritmatika berarti penyortiran terkait dengan jenis penghitungan.
Menghitung Macam
Ide dasarnya adalah bahwa kita menghitung berapa angka di setiap kelas.
Sorting sorting :: Counting sort
Kami menghitung berapa kali satu atau nomor lainnya terjadi dalam array. Mengetahui jumlah ini, kami dengan cepat membentuk array yang sudah dipesan.
Untuk pengurutan ini, Anda perlu mengetahui minimum dan maksimum dalam array. Kemudian kunci dihasilkan untuk array bantu, di mana kami memperbaiki apa dan berapa kali bertemu.
Kode Python:
def CountingSort(array, mn, mx): count = defaultdict(int) for i in array: count[i] += 1 result = [] for j in range(mn,mx+1): result += [j]* count[j] return result
Pigeon Sort :: Pigeonhole sort
Kami pergi melalui array, jika nomor baru ditemukan, maka kami memulai penghitung (sebagai kunci dari daftar tambahan) dari nomor ini. Jika nomor yang ditemui bukan untuk pertama kalinya, maka kenaikan untuk penghitung ini dipicu.
Perbedaan dari metode sebelumnya adalah bahwa dalam menyortir dengan menghitung, kami segera memulai penghitung untuk semua angka yang mungkin terjadi dalam array (kami dapat membelinya jika diketahui maksimum dan minimum dalam array). Beberapa angka tidak pernah muncul dan penghitungnya menunjukkan nol. Dalam penyortiran merpati, kita mulai penghitung hanya untuk angka-angka yang benar-benar terjadi dalam array. Array digunakan dalam menghitung penyortiran untuk penghitung, dan daftar tertaut ganda digunakan dalam penyortiran merpati, yang memungkinkan menambahkan penghitung baru saat bepergian.
Metode ini kadang-kadang secara alternatif disebut
Penyortiran Dirichlet , karena algoritma itu sendiri adalah ilustrasi dari berbagai konsekuensi dari prinsip Dirichlet.
Jika N objek didistribusikan di wadah M, dan N> M, maka setidaknya satu wadah berisi lebih dari satu elemen.
Kode Python:
def PigeOnHoleSort(a): mi = min(a) size = max(a) - mi + 1 holes = [0] * size for x in a: holes[x - mi] += 1 i = 0 for count in range(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + mi i += 1
Sortasi bit
Kami mendistribusikan angka-angka tergantung pada digit mana yang berada dalam kategori nomor tertentu. Jika kita melakukan ini beberapa kali untuk digit yang berbeda, maka kita tiba-tiba mendapatkan array yang diurutkan.
Pengurutan bitwise orde rendah :: LSD radix sort
Kami bergerak dari angka yang lebih rendah ke yang lebih lama dan pada setiap iterasi kami mendistribusikan elemen-elemen dari array tergantung pada digit apa yang ada di digit tersebut.
Setelah distribusi berikutnya, kami mengembalikan elemen ke array utama dalam urutan di mana elemen jatuh ke dalam kelas selama redistribusi berikutnya.
Untuk penyortiran bitwise, penting agar elemen dianggap memiliki jumlah digit yang sama. Jika jumlah aktual digit berbeda, maka masalahnya diselesaikan dengan menambahkan nol tambahan sebagai digit lebih tinggi.
Pengurutan bitwise orde tinggi :: Urutan MSD radix
Pertama, kami mendistribusikan di antara peringkat senior, dari mana kami pindah ke yang lebih muda.
Opsi ini lebih sulit untuk diimplementasikan, karena transisi ke digit yang lebih rendah dilakukan secara rekursif di dalam kelas, dan bukan di antara semua elemen array.
Tetapi kompleksitas ini dihargai oleh fakta bahwa MSD lebih cepat daripada LSD. Saat melewati dari angka yang lebih rendah ke angka yang lebih tua, Anda harus memproses semua digit dari semua angka untuk mengurutkan dengan benar. Jika Anda berpindah dari senior ke muda, maka sebenarnya Anda tidak harus memproses semua digit semua angka, negara yang disortir, sebagai aturan, datang lebih awal.
Sebagian besar penyortiran bitwise adalah variasi dari MSD yang lebih efisien. Ini sangat berguna untuk menyortir string, karena ini, pohon suffix biasanya digunakan. Kami akan menganalisis dalam salah satu artikel berikut.
Menghitung penyortiran bitwise
Kadang-kadang penyortiran distribusi secara bersamaan dihitung dan bitwise.
Bead Sort :: Manik sort
Nama lain dari algoritma: penyortiran sempoa, penyortiran gravitasi.
Saya sudah menulis tentang penyortiran ini beberapa kali (
1 ,
2 ), jadi saya akan singkat, hanya intinya.
Misalkan setiap angka dalam array adalah satu set bola, jumlah bola adalah nilai angka. Jika kita mengatur angka satu sama lain sebagai baris horizontal dari bola-bola ini dan kemudian mendorongnya secara vertikal, kita mendapatkan susunan yang teratur.
Kuncinya di sini adalah bahwa kami mewakili setiap angka menggunakan bola dalam sistem angka unary. Dan faktanya, kita cukup menghitung berapa kali semua angka memiliki setiap digit.
BeadSort dalam Python dalam satu baris:
Setelah beberapa saat, kami akan menganalisis penyortiran penghitungan bitwise yang lebih kompleks, di antaranya penyortiran
bendera Amerika menempati tempat yang menonjol.
Referensi
Ember /
Ember ,
Menghitung /
Lubang Pigeon /
Dirichlet ,
Radix /
Pelepasan ,
ManikArtikel Seri:
Aplikasi AlgoLab Excel telah diperbarui secara signifikan. Beberapa algoritma dari artikel hari ini muncul di sana untuk pertama kalinya. Perbarui siapa yang menggunakan.