Geekly articles weekly

Sortir Bendera Amerika


Untuk memahami prinsip pengoperasian penyortiran "multiband" ini, lebih mudah untuk memulai dengan contoh bendera dengan tiga garis. Dan agar dapat dengan mudah menangani bendera tiga warna, lebih baik untuk pertama kali melihat cara kerjanya dengan contoh dua warna. Dan untuk berurusan dengan dua warna ...
Perangkat Lunak EDISON - pengembangan web
Artikel ini ditulis dengan dukungan EDISON.

Kami terlibat dalam porting dan migrasi perangkat lunak , serta pengembangan aplikasi mobile Android dan iOS .

Kami menyukai teori algoritma! ;-)

Bendera dua warna



Pertama, pertimbangkan kasus ketika angka-angka dalam array yang diurutkan didistribusikan hanya dalam dua bit. Untuk kesederhanaan, kami menganggap bahwa kami memiliki array nol (urutan rendah) dan yang (urutan tinggi).

Dengan demikian, kita hanya memiliki dua "band": dalam satu kita akan memindahkan bit paling signifikan (nol), dan yang lain bit (unit) tertinggi. Bendera dua warna akan diperlihatkan untuk demonstrasi. Misalnya, bendera Ukraina.



Apa yang sedang terjadi di sini? Karena pada tahap pertama tidak diketahui berapa angka nol dan berapa unit yang kita miliki, oleh karena itu tidak jelas ukuran masing-masing "band" tersebut. Oleh karena itu, kami meletakkan dua pointer pada kunci-kunci array. Untuk urutan rendah, penunjuk diatur ke awal array, untuk urutan tinggi - hingga akhir. Kemudian kami membuat satu melewati array dari kiri ke kanan dan melihat setiap elemen bit.

Jika selama bagian elemen sama dengan urutan tertinggi, maka pointer kedua memberitahu kita di mana untuk mentransfer elemen ini (kami melakukan pertukaran). Pointer untuk memasukkan elemen berikutnya bergerak ke kiri, "strip" untuk digit senior telah diperluas.

Jika itu sama dengan digit paling signifikan, maka kita memindahkan pointer untuk itu satu elemen ke kanan. Karena kita hanya memiliki dua digit, tidak perlu mentransfer elemen, itu sudah ada di tempatnya. "Strip" untuk kategori yang lebih muda secara alami menjadi lebih luas.

Akibatnya, dua petunjuk yang bergerak ke arah satu sama lain akan bertabrakan pada satu titik, dan muatan akan dipesan di "band" mereka. Pada saat yang sama, Anda tidak perlu melewati seluruh array - ketika pointer bertemu di suatu tempat di tengah, algoritma akan melakukan tugasnya.

Masalah Bendera Nasional Belanda :: Masalah bendera nasional Belanda



Kami sedikit menyulitkan tugas, pertimbangkan bukan dua digit, tetapi tiga. Mari kita memiliki elemen-elemen array milik digit terendah (nol), menengah (unit) dan senior (dua).

Sebagai demonstrasi, kami mengambil bendera tiga arah merah putih-putih Prancis, Luksemburg Rusia, Schleswig-Goldstein dari Belanda. Mengapa tepatnya bendera Belanda? Karena Edsger Dijkstra dalam ceramahnya tentang contoh bendera ini memeriksa algoritma yang sesuai, yang disebut "tugas bendera nasional Belanda."



Seperti yang Anda lihat, tidak ada yang baru. Setiap kategori memiliki pointer sendiri. Awalnya, label untuk junior dan menengah mengambil posisi awal di awal array dan bergerak ke kanan ketika elemen yang sesuai ditemui. Pointer untuk orde tinggi pertama di ujung array dan bergerak ke kiri.

Melewati array juga tidak akan lengkap, jika bit-bitnya kurang lebih terdistribusi secara merata, maka algoritma akan melewati 2/3 dari array sebelum menghamburkan semua elemen dalam "band" -nya.

Jenis bendera Amerika :: Jenis bendera Amerika



Sekarang, dalam penjelasan kami, kami dapat beralih ke bendera Amerika multiband.

Ketika kita tidak memiliki dua, bukan tiga, tetapi sejumlah digit, kita menetapkan di mana setiap digit harus dimulai ("band" -nya) dan menggambar ulang elemen dalam "band" mereka.

Dalam algoritma ini, angka biasanya dianggap bukan sebagai desimal, tetapi dalam kedalaman bit yang berbeda, paling sering menjadi kekuatan dua. Seringkali, angka 256 diambil sebagai dasar untuk kedalaman bit (agak kurang dari 128), yang memungkinkan Anda untuk mengadaptasi penyortiran secara efisien untuk mengatur string. Untuk angka untuk kedalaman bit, lebih mudah untuk mengambil kecil 2 n (2, 4, 16, dll.), Yang memungkinkan Anda untuk membandingkan dengan menggeser bit, alih-alih naik ke daya saat membandingkan angka desimal.

Animasi ini menunjukkan contoh kedalaman bit dengan basis 16:



  1. Pada pass pertama - cari maksimum untuk menentukan jumlah bit maksimum di antara elemen dalam array (untuk mengekstrak bit yang ditentukan dengan benar dari akun dari elemen).
  2. Kemudian terjadi proses rekursif. Ketika dipanggil, batas-batas subarray dan bit yang diproses saat ini ditunjukkan. Pada panggilan pertama, seluruh array adalah sebuah subarray, bit pertama di sebelah kiri diambil.
  3. Di antara elemen-elemen subarray, perhitungan awal dilakukan - berapa kali setiap digit terjadi dalam kategori saat ini. Hitungan ini memungkinkan Anda untuk menentukan lokalisasi untuk digit-digit ini (yaitu, batas dan lokasi "strip" yang ingin Anda pindahkan elemen-elemen yang memiliki digit berikutnya dalam digit tertentu diketahui). Bahkan, pelokalan adalah petunjuk untuk "band" di mana elemen yang sesuai harus dipindahkan.
  4. Sesuai dengan penunjuk-lokalisasi, pertukaran terjadi di tempat - digit dalam kategori menunjukkan di mana Anda ingin mengirim barang, di tempat itu muncul item lain yang dengannya pertukaran terjadi. Klausa ini dieksekusi sampai pertukaran berikutnya, elemen yang datang dari tempat lain tidak ada di tempatnya (maka Anda dapat beralih ke elemen subarray berikutnya dan melakukan klausa ini untuknya).
  5. Setelah pertukaran mendistribusikan elemen ke blok dengan angka di digit berikutnya, rekursi terjadi - algoritma yang sama diterapkan ke setiap blok sebagai subarray, yang berikutnya diambil sebagai digit saat ini.

Dalam artikel tentang menghitung jenis dengan distribusi perkiraan, ada algoritma yang sangat mirip secara visual - pengurutan aproksimasi . Di sana kami menghitung berapa kali setiap angka dalam array terjadi - dan mendistribusikan kembali elemen sesuai dengan lokalisasi yang diperoleh. Di sini kami menghitung berapa kali setiap digit dalam kategori terjadi untuk elemen subarray - dan kami juga mendistribusikan ulang elemen dalam subarray sesuai dengan pelokalan yang diperoleh. Jika aproksimasi adalah semacam penghitungan, maka "Amerika" adalah penyortiran penghitungan-bit.

Sortir Bendera Amerika - Implementasi Python
#           def get_radix_val(x, digit, radix) -> int: return int(floor(x / radix**digit)) % radix #             def compute_offsets(a_list, start: int, end: int, digit, radix) -> list: #          counts = [0 for _ in range(radix)] for i in range(start, end): #        #         val = get_radix_val(a_list[i], digit, radix) counts[val] += 1 #       #          offsets = [0 for _ in range(radix)] sum = 0 #         for i in range(radix): offsets[i] = sum sum += counts[i] return offsets #      def swap(a_list, offsets, start: int, end: int, digit, radix) -> None: i = start #          next_free = copy(offsets) #        #   (       ) cur_block = 0 while cur_block < radix-1: # if i >= start + offsets[cur_block+1]: cur_block += 1 continue radix_val = get_radix_val(a_list[i], digit, radix) if radix_val == cur_block: i += 1 continue swap_to = next_free[radix_val] a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i] next_free[radix_val] += 1 #   def american_flag_sort_helper(a_list, start: int, end: int, digit, radix) -> None: #          offsets = compute_offsets(a_list, start, end, digit, radix) #      swap(a_list, offsets, start, end, digit, radix) if digit == 0: #     ? return #   #       for i in range(len(offsets)-1): #      #         american_flag_sort_helper(a_list, offsets[i], offsets[i+1], digit-1, radix) #   def american_flag_sort(a_list, radix) -> None: #,         for x in a_list: assert(type(x) == int) #    max_val = max(a_list) #    (  ) max_digit = int(floor(log(max_val, radix))) #   -     american_flag_sort_helper(a_list, 0, len(a_list), max_digit, radix)

Sortir ska :: Sortir ska


Programmer Jerman, Malte Skarupke, mengumumkan bahwa ia telah mengembangkan algoritme penyortiran baru, yang merupakan “bendera Amerika” yang ditingkatkan secara radikal dan mengungguli std :: sort rata-rata 2 kali (std :: sort - sebuah algoritma yang juga dikenal sebagai penyortiran introspektif - hibrida dari penyortiran cepat dan penyortiran berdasarkan tumpukan ).

  1. Array diurutkan secara rekursif, pada tingkat rekursi pertama, seluruh array diambil sebagai subarray.
  2. Jika subarray memiliki kurang dari 128 elemen, maka std :: sort dipanggil untuknya.
  3. Jika subarray berisi dari 128 hingga 1024 elemen, maka penyortiran bendera Amerika dipanggil untuk itu.
  4. Jika ada lebih dari 1024 elemen dalam subarray, maka pengurutan ska diperlukan untuk itu.
  5. Juga, untuk menghindari kasus terburuk, jika nesting rekursif terlalu besar (lebih dari 16 level), algoritme beralih ke std :: sort , bahkan jika ada lebih dari 128 elemen dalam subarray.

Tampaknya, ini adalah algoritma yang sangat efektif dan pada saat yang sama sangat kompleks - implementasi penulisnya membutuhkan hampir satu setengah ribu baris. Mungkin kita akan mempertimbangkan penyortiran ini suatu hari nanti, sekarang kita tidak akan membahasnya. Mereka yang tertarik dapat mengklik tautan di bawah ini.

Referensi


Masalah bendera nasional Belanda , semacam bendera Amerika

Sortir ska: Saya Menulis Algoritma Penyortiran Lebih Cepat ( Bagian 1 , Bagian 2 ) Kode github

Artikel Seri:


Dalam aplikasi AlgoLab Excel, pengurutan dengan bendera dua warna (sort nol dan satu), bendera tiga warna (sort nol, satu dan deuces), pengurutan berdasarkan bendera Amerika muncul. Untuk mengurutkan "Bendera Amerika", Anda dapat (dalam komentar di sel dengan nama algoritma) menentukan sistem angka untuk distribusi - standarnya adalah heksadesimal.

Source: https://habr.com/ru/post/id481304/

More articles:


All Articles