Geekly articles weekly

Perkiraan penghitungan distribusi - paling sering penyortiran ulang


Jumlah yang kurang lebih berbeda satu sama lain dijamin lebih dari seratus. Di antara mereka ada subkelompok algoritma yang minimal berbeda satu sama lain, bertepatan dalam beberapa gagasan utama umum. Faktanya, pada tahun-tahun yang berbeda, orang yang berbeda muncul dengan penyortiran yang sama lagi, berbeda dalam rincian yang tidak terlalu mendasar.

Gagasan algoritmik seperti itu lebih sering ditemukan daripada yang lain.

Setiap elemen dimasukkan kira-kira di tempat array di mana ia seharusnya berada. Ternyata array yang hampir dipesan . Di mana penyortiran berdasarkan sisipan diterapkan (paling efektif untuk memproses array yang hampir dipesan) atau area unordered lokal diproses secara rekursif oleh algoritma yang sama.

Perangkat Lunak EDISON - pengembangan web
Artikel ini ditulis dengan dukungan EDISON, yang mengembangkan berbagai solusi untuk berbagai tugas: dari program online mencoba pakaian toko multi-merek hingga sistem transmisi LED antara kapal sungai dan laut .

Kami menyukai teori algoritma! ;-)
Untuk mengevaluasi kira-kira di mana Anda ingin meletakkan elemen, Anda perlu mencari tahu berapa banyak berbeda dari elemen rata-rata array. Untuk melakukan ini, Anda perlu mengetahui nilai-nilai elemen minimum dan maksimum, baik, dan ukuran array.

Array yang diurutkan seharusnya memiliki data yang benar-benar acak. Semua penemu metode ini memiliki rumus yang sama:


k adalah tempat perkiraan dalam array tempat elemen A ( i ) seharusnya berada
min , maks - nilai elemen minimum dan maksimum dalam array A
Ukuran - jumlah elemen dalam array A

Ini ide yang umum. Mari kita lihat variasi mana dari algoritma ini yang dilahirkan berulang kali.

Sorting King Solomon :: Sort Solomon



Metode ini (dan namanya yang indah) diusulkan oleh pengguna V2008n sekitar 5 tahun yang lalu. Ada waktu untuk segalanya, “ada waktu untuk menaburkan batu dan ada waktu untuk mengumpulkan batu” (kata-kata Raja Salomo dari buku Pengkhotbah) - dan dalam algoritme, inilah yang terjadi. Pertama, dengan bantuan rumus, kami menyebarkan elemen di tempat yang diinginkan dalam array. Karena formula tidak memberikan tempat yang tepat, tetapi perkiraan, beberapa elemen yang dekat satu sama lain dalam nilai mengklaim beberapa posisi sekaligus. Grup elemen lokal ini diurutkan berdasarkan sisipan dan kemudian disusun dalam urutan akhir.

Urutan interpolasi


"Tidak ada yang baru di bawah matahari," mengutip penulis yang sama lagi. Wikipedia menjelaskan penyortiran dengan interpolasi, yang secara mencurigakan mengingatkan pada penyortiran Solomon. Setiap “tumpukan batu” adalah susunan dinamis kecil tambahan, tempat elemen-elemen yang sama pentingnya berada. Perbedaan utama adalah bahwa setelah “penghamburan batu” kelompok-kelompok elemen lokal yang tidak disortir ini diurutkan bukan oleh sisipan, tetapi dengan menyortir diri mereka dengan interpolasi (secara rekursif atau dalam satu lingkaran).

Array yang dipesan adalah kumpulan data diskrit yang dapat dianggap sebagai himpunan terbatas dari nilai yang diketahui dari fungsi tertentu yang tidak diketahui. Sebenarnya, perkiraan distribusi dari sudut pandang matematika komputasi - ini adalah interpolasi.

Urutan Interpolasi JavaScript - Loopback
Array.prototype.interpolationSort = function() { var divideSize = new Array(); var end = this.length; divideSize[0] = end; while(divideSize.length > 0) {divide(this);} function divide(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; var temp = 0; for(var i = start + 1; i < end; i++) { if(A[i] < min) { min = A[i]; } else { if(A[i] > max) {max = A[i];} } } if(min == max) { end = end - size; } else { var p = 0; var bucket = new Array(size); for(var i = 0; i < size; i++) {bucket[i] = new Array();} for(var i = start; i < end; i++) { p = Math.floor(((A[i] - min) / (max - min)) * (size - 1)); bucket[p].push(A[i]); } for(var i = 0; i < size; i++) { if(bucket[i].length > 0) { for(var j = 0; j < bucket[i].length; j++) {A[start++] = bucket[i][j];} divideSize.push(bucket[i].length); } } } } };

Urutan interpolasi JavaScript - versi rekursif
 Array.prototype.bucketSort = function() { var start = 0; var size = this.length; var min = this[0]; var max = this[0]; for(var i = 1; i < size; i++) { if (this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } } if(min != max) { var bucket = new Array(size); for(var i = 0; i < size; i++) {bucket[i] = new Array();} var interpolation = 0; for(var i = 0; i < size; i++){ interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1)); bucket[interpolation].push(this[i]); } for(var i = 0; i < size; i++) { if(bucket[i].length > 1) {bucket[i].bucketSort();} //Recursion for(var j = 0; j < bucket[i].length; j++) {this[start++] = bucket[i][j];} } } };

Sortir histogram :: Sortir histogram


Ini adalah optimasi penyortiran berdasarkan interpolasi, yang menghitung jumlah elemen yang dimiliki grup lokal yang tidak disortir. Hitungan ini memungkinkan Anda untuk memasukkan item yang tidak disortir langsung ke dalam array yang dihasilkan (alih-alih mengelompokkannya ke dalam array kecil yang terpisah).

Sortir Bilah JavaScript
 Array.prototype.histogramSort = function() { var end = this.length; var sortedArray = new Array(end); var interpolation = new Array(end); var hitCount = new Array(end); var divideSize = new Array(); divideSize[0] = end; while(divideSize.length > 0) {distribute(this);} function distribute(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; for(var i = start + 1; i < end; i++) { if (A[i] < min) { min = A[i]; } else { if (A[i] > max) {max = A[i];} } } if (min == max) { end = end - size; } else { for(var i = start; i < end; i++){hitCount[i] = 0;} for(var i = start; i < end; i++) { interpolation[i] = start + Math.floor(((A[i] - min) / (max - min)) * (size - 1)); hitCount[interpolation[i]]++; } for(var i = start; i < end; i++) { if(hitCount[i] > 0){divideSize.push(hitCount[i]);} } hitCount[end - 1] = end - hitCount[end - 1]; for(var i = end - 1; i > start; i--) { hitCount[i - 1] = hitCount[i] - hitCount[i - 1]; } for(var i = start; i < end; i++) { sortedArray[hitCount[interpolation[i]]] = A[i]; hitCount[interpolation[i]]++; } for(var i = start; i < end; i++) {A[i] = sortedArray[i];} } } };

Urutan tag interpolasi


Untuk lebih mengoptimalkan overhead, disarankan di sini untuk mengingat bukan jumlah elemen yang sama dalam kelompok yang tidak disortir, tetapi cukup menandai awal dari grup ini dengan bendera Benar / Salah. Benar berarti bahwa subkelompok sudah diurutkan, dan Salah berarti belum.

Jenis interpolasi tagged JavaScript
 Array.prototype.InterpolaionTagSort = function() { var end = this.length; if(end > 1) { var start = 0 ; var Tag = new Array(end); //Algorithm step-1 for(var i = 0; i < end; i++) {Tag[i] = false;} Divide(this); } //Algorithm step-2 while(end > 1) { while(Tag[--start] == false){} //Find the next bucket's start Divide(this); } function Divide(A) { var min = A[start]; var max = A[start]; for(var i = start + 1; i < end; i++) { if(A[i] < min) { min = A[i]; } else { if(A[i] > max ) {max = A[i];} } } if(min == max) { end = start; } else { //Algorithm step-3 Start to be the next bucket's end var interpolation = 0; var size = end - start; var Bucket = new Array(size);//Algorithm step-4 for(var i = 0; i < size; i++) {Bucket[i] = new Array();} for(var i = start; i < end; i++) { interpolation = Math.floor(((A[i] - min) / (max - min)) * (size - 1)); Bucket[interpolation].push(A[i]); } for(var i = 0; i < size; i++) { if(Bucket[i].length > 0) {//Algorithm step-5 Tag[start] = true; for(var j = 0; j < Bucket[i].length; j++) {A[start++] = Bucket[i][j];} } } } }//Algorithm step-6 };

Urutan tag interpolasi (di tempat)


Jika nilai-nilai elemen dalam array tidak diulang dan didistribusikan secara merata (secara kasar - jika data dalam bentuk yang diurutkan adalah seperti perkembangan aritmatika), maka Anda dapat mengurutkan dalam satu lintasan, menyortir tepat di tempatnya, tanpa memindahkan elemen ke array perantara.

Urutkan berdasarkan interpolasi dengan label (di tempat) dalam JavaScript
 Array.prototype.InPlaceTagSort = function() { var n = this.length; var Tag = new Array(n); for(i = 0; i < n; i++) {Tag[i] = false;} var min = this[0]; var max = this[0]; for(i = 1; i < n; i++) { if(this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } } var p = 0; var temp = 0; for(i = 0; i < n; i++) { while(Tag[i] == false) { p = Math.floor(((this[i] - min) / (max - min)) * (n - 1)); temp = this[i]; this[i] = this[p]; this[p] = temp; Tag[p] = true; } } };

Sortir Flash :: Flashsort


Suatu ketika, saya menulis tentang penyortiran, yang ditemukan oleh profesor biofisika Neubert pada tahun 1998.

Profesor menyarankan untuk mendistribusikan elemen ke dalam beberapa kelas terpisah (keanggotaan kelas ditentukan oleh ukuran elemen). Dengan mengingat hal ini, rumusnya terlihat seperti ini:


Alih-alih Ukuran (ukuran array), rumus menunjukkan m - jumlah kelas dimana kita mendistribusikan elemen-elemen array. Rumus tidak menghitung kunci dalam array tempat elemen harus dilemparkan, tetapi nomor kelas tempat elemen tersebut berada.

Penyortiran ini tidak buruk karena lebih hemat soal memori tambahan. Redistribusi elemen terjadi pada tempatnya. Hanya lokalisasi kelas yang disimpan secara terpisah (well, jika Anda melihat dari sudut yang berbeda, jumlah elemen milik kelas tertentu disimpan secara terpisah).

Nah, sisanya adalah lagu yang sama.


Sortir Flash di Jawa
 /** * FlashSort.java - integer version * Translation of Karl-Dietrich Neubert's algorithm into Java by * Rosanne Zhang */ class FlashSort { static int n; static int m; static int[] a; static int[] l; /* constructor @param size of the array to be sorted */ public static void flashSort(int size) { n = size; generateRandomArray(); long start = System.currentTimeMillis(); partialFlashSort(); long mid = System.currentTimeMillis(); insertionSort(); long end = System.currentTimeMillis(); // print the time result System.out.println("Partial flash sort time : " + (mid - start)); System.out.println("Straight insertion sort time: " + (end - mid)); } /* Entry point */ public static void main(String[] args) { int size = 0; if (args.length == 0) { usage(); System.exit(1); } try { size = Integer.parseInt(args[0]); } catch (NumberFormatException nfe) { usage(); System.exit(1); } FlashSort.flashSort(size); } /* Print usage */ private static void usage() { System.out.println(); System.out.println("Usage: java FlashSort n "); System.out.println(" n is size of array to sort"); } /* Generate the random array */ private static void generateRandomArray() { a = new int[n]; for(int i=0; i < n; i++) { a[i] = (int)(Math.random() * 5 * n); } m = n / 20; l = new int[m]; } /* Partial flash sort */ private static void partialFlashSort() { int i = 0, j = 0, k = 0; int anmin = a[0]; int nmax = 0; for(i=1; i < n; i++) { if (a[i] < anmin) anmin=a[i]; if (a[i] > a[nmax]) nmax=i; } if(anmin == a[nmax]) return; double c1 = ((double)m - 1) / (a[nmax] - anmin); for(i=0; i < n; i++) { k= (int) (c1 * (a[i] - anmin)); l[k]++; } for(k=1; k < m; k++) { l[k] += l[k - 1]; } int hold = a[nmax]; a[nmax] = a[0]; a[0] = hold; int nmove = 0; int flash; j = 0; k = m - 1; while(nmove < n - 1) { while(j > (l[k] - 1)) { j++; k = (int) (c1 * (a[j] - anmin)); } flash = a[j]; while(!(j == l[k])) { k = (int) (c1 * (flash - anmin)); hold = a[l[k] - 1]; a[l[k] - 1] = flash; flash = hold; l[k]--; nmove++; } } } /* Straight insertion sort */ private static void insertionSort() { int i, j, hold; for(i = a.length - 3; i >= 0; i--) { if(a[i + 1] < a[i]) { hold = a[i]; j = i; while (a[j + 1] < hold) { a[j] = a[j + 1]; j++; } a[j] = hold; } } } /* For checking sorting result and the distribution */ private static void printArray(int[] ary) { for(int i=0; i < ary.length; i++) { if((i + 1) % 10 ==0) { System.out.println(ary[i]); } else { System.out.print(ary[i] + " "); } System.out.println(); } } }

Approximate Sort :: Proxmap sort


Penyortiran ini adalah yang tertua dari yang disebutkan di sini, diperkenalkan pada tahun 1980 oleh Profesor Thomas Standish dari University of California. Secara penampilan, tampaknya sangat berbeda, tetapi jika Anda perhatikan lebih dekat, semuanya sama.

Algoritma beroperasi dengan konsep seperti hit - angka tertentu yang dekat nilainya dengan beberapa elemen array.
Untuk menentukan apakah elemen array adalah hit, fungsi aproksimasi diterapkan ke elemen.

Profesor Standish mengurutkan susunan bilangan real. Fungsi aproksimasi adalah untuk membulatkan bilangan real ke bilangan bulat.
Misalnya, jika array berisi elemen 2.8, 2, 2.1, 2.6, dll. maka hit untuk angka-angka ini akan menjadi deuce.



Prosedur umum:

  1. Kami menerapkan fungsi perkiraan untuk setiap elemen, menentukan klik mana yang sesuai dengan elemen berikutnya.
  2. Jadi, untuk setiap klik, kita dapat menghitung jumlah elemen yang sesuai dengan klik ini.
  3. Mengetahui jumlah elemen untuk semua hit, kami menentukan lokalisasi hit (berbatasan di sebelah kiri) dalam array.
  4. Mengetahui pelokalan hit, kami menentukan lokalisasi setiap elemen.
  5. Setelah menentukan lokalisasi elemen, kami mencoba memasukkannya di tempatnya dalam array. Jika tempat sudah diambil, maka kami memindahkan tetangga ke kanan (jika elemen lebih kecil dari mereka) untuk memberikan ruang bagi elemen. Atau ke kanan kita memasukkan elemen itu sendiri (jika lebih dari tetangga).

Sebagai fungsi perkiraan, Anda dapat menetapkan satu berdasarkan sifat umum dari data dalam array. Dalam implementasi modern penyortiran ini, hit biasanya ditentukan bukan dengan menggigit bagian pecahan, tetapi menggunakan formula favorit kami.

Jenis perkiraan JavaScript
 Array.prototype.ProxmapSort = function() { var start = 0; var end = this.length; var A2 = new Array(end); var MapKey = new Array(end); var hitCount = new Array(end); for(var i = start; i < end; i++) {hitCount[i] = 0;} var min = this[start]; var max = this[start]; for (var i = start+1; i < end; i++){ if (this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } } //Optimization 1.Save the MapKey[i]. for (var i = start; i < end; i++) { MapKey[i] = Math.floor(((this[i] - min ) / (max - min)) * (end - 1)); hitCount[MapKey[i]]++; } //Optimization 2.ProxMaps store in the hitCount. hitCount[end-1] = end - hitCount[end - 1]; for(var i = end-1; i > start; i--){ hitCount[i-1] = hitCount[i] - hitCount[i - 1]; } //insert A[i]=this[i] to A2 correct position var insertIndex = 0; var insertStart = 0; for(var i = start; i < end; i++){ insertIndex = hitCount[MapKey[i]]; insertStart = insertIndex; while(A2[insertIndex] != null) {insertIndex++;} while(insertIndex > insertStart && this[i] < A2[insertIndex - 1]) { A2[insertIndex] = A2[insertIndex - 1]; insertIndex--; } A2[insertIndex] = this[i]; } for(var i = start; i < end; i++) {this[i] = A2[i];} };

Penyortiran sisipan hash jenis: Menyortir hash


Baiklah, kami akan mengakhiri ulasan kami dengan algoritme yang disarankan oleh bobbyKdas habraiser 6 tahun yang lalu. Ini adalah algoritma hybrid di mana, selain distribusi dan memasukkan, penggabungan juga ditambahkan.

  1. Array dibagi secara setengah menjadi setengahnya, sampai pada suatu langkah ukuran setengah-setengah mencapai ukuran minimum (penulis tidak memiliki lebih dari 500 elemen).
  2. Pada tingkat rekursi terendah, algoritme yang akrab diterapkan pada masing-masing setengah subarray - menggunakan rumus yang sama, distribusi perkiraan terjadi di dalam subarray, dengan pengurutan berdasarkan sisipan bagian yang tidak disortir lokal.
  3. Setelah pengaturan dua bagian dari subarrays, mereka bergabung.
  4. Poin 3 (penggabungan setengah bagian yang diurutkan) diulangi saat naik melalui tingkat rekursi ke bagian paling atas, ketika array asli digabungkan dari dua bagian.

Urutkan dengan memasukkan hash di Jawa
 import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort { //    static int SOURCELEN = 1000000; int source[] = new int[SOURCELEN]; //        int quick[] = new int[SOURCELEN]; //     static int SORTBLOCK = 500; static int k = 3; //  static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN; int tmp[] = new int[TMPLEN]; //    static int MIN_VAL = 10; static int MAX_VAL = 1000000; int minValue = 0; int maxValue = 0; double hashKoef = 0; //      public void randomize() { int i; Random rnd = new Random(); for(i=0; i<SOURCELEN; i++) { int rndValue = MIN_VAL + ((int)(rnd.nextDouble()*((double)MAX_VAL-MIN_VAL))); source[i] = rndValue; } } //         - public void findMinMax(int startIndex, int endIndex) { int i; minValue = source[startIndex]; maxValue = source[startIndex]; for(i=startIndex+1; i<=endIndex; i++) { if( source[i] > maxValue) { maxValue = source[i]; } if( source[i] < minValue) { minValue = source[i]; } } hashKoef = ((double)(k-1)*0.9)*((double)(endIndex-startIndex)/((double)maxValue-(double)minValue)); } // (  - )      public void stickParts(int startIndex, int mediana, int endIndex) { int i=startIndex; int j=mediana+1; int k=0; //      -    while(i<=mediana && j<=endIndex) { if(source[i]<source[j]) { tmp[k] = source[i]; i++; } else { tmp[k] = source[j]; j++; } k++; } //     -      if( i>mediana ) { while(j<=endIndex) { tmp[k] = source[j]; j++; k++; } } //     -      if(j>endIndex) { while(i<=mediana) { tmp[k] = source[i]; i++; k++; } } System.arraycopy(tmp, 0, source, startIndex, endIndex-startIndex+1); } //        //         boolean shiftRight(int index) { int endpos = index; while( tmp[endpos] != 0) { endpos++; if(endpos == TMPLEN) return false; } while(endpos != index ) { tmp[endpos] = tmp[endpos-1]; endpos--; } tmp[endpos] = 0; return true; } //-    public int hash(int value) { return (int)(((double)value - (double)minValue)*hashKoef); } //        public void insertValue(int index, int value) { int _index = index; //  ,    //            - while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; } //       ,    if( tmp[_index] != 0) { shiftRight(_index);//      } tmp[_index] = value;//  -   } //        public void extract(int startIndex, int endIndex) { int j=startIndex; for(int i=0; i<(SORTBLOCK*k); i++) { if(tmp[i] != 0) { source[j] = tmp[i]; j++; } } } //   public void clearTMP() { if( tmp.length < SORTBLOCK*k) { Arrays.fill(tmp, 0); } else { Arrays.fill(tmp, 0, SORTBLOCK*k, 0); } } //  public void hashingSort(int startIndex, int endIndex) { //1.          findMinMax(startIndex, endIndex); //2.    clearTMP(); //3.       - for(int i=startIndex; i<=endIndex; i++) { insertValue(hash(source[i]), source[i]); } //4.         extract(startIndex, endIndex); } //         public void sortPart(int startIndex, int endIndex) { //    500,   - if((endIndex - startIndex) <= SORTBLOCK ) { hashingSort(startIndex, endIndex); return; } //  > 500         int mediana = startIndex + (endIndex - startIndex) / 2; sortPart(startIndex, mediana);//    sortPart(mediana+1, endIndex);//    stickParts(startIndex, mediana, endIndex);//   -   } //       public void sort() { sortPart(0, SOURCELEN-1); } public static void main(String[] args) { HashSort hs = new HashSort(); hs.randomize(); hs.sort(); } }

Rumus itu sendiri disebut fungsi hash, dan array bantu untuk perkiraan distribusi disebut tabel hash.

Referensi


Interpolasi & Histogram , Flash , Proxmap

Solomon , Hash Table , Flash

Artikel Seri:



Penyortiran perkiraan muncul dalam aplikasi AlgoLab Excel (dalam hal ini, dalam array awal yang tidak disortir, bagian pecahan acak ditambahkan ke bilangan bulat). Solomon dan Flash telah ada di sana untuk waktu yang lama, tetapi belum menerapkan interpolasi, hash, dan histogram.

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

More articles:


All Articles