Geekly articles weekly

GeschÀtzte VerteilungszÀhlung - am hÀufigsten neu erfundene Sortierung


Die Anzahl der mehr oder weniger unterschiedlichen Sorten betrÀgt garantiert mehr als hundert. Unter ihnen gibt es Untergruppen von Algorithmen, die sich minimal voneinander unterscheiden und in einer allgemeinen Grundidee zusammenfallen. In der Tat kommen in verschiedenen Jahren verschiedene Menschen auf die gleichen Sortierungen, die sich in nicht sehr grundlegenden Details unterscheiden.

Eine solche algorithmische Idee kommt hÀufiger vor als andere.

Jedes Element wird ungefĂ€hr an der Stelle des Arrays eingegeben , an der es sich befinden soll. Es stellt sich ein fast geordnetes Array heraus. Auf welche Sortierung durch EinfĂŒgungen angewendet wird (dies ist am effektivsten fĂŒr die Verarbeitung von fast geordneten Arrays) oder lokale ungeordnete Bereiche werden nach demselben Algorithmus rekursiv verarbeitet.

EDISON Software - Webentwicklung
Dieser Artikel wurde mit UnterstĂŒtzung von EDISON verfasst, das eine breite Palette von Lösungen fĂŒr eine Vielzahl von Aufgaben entwickelt: von Programmen zum Online-Anprobieren von Kleidung in MehrmarkengeschĂ€ften bis zu einem LED-Übertragungssystem zwischen Fluss- und Seeschiffen .

Wir lieben die Theorie der Algorithmen! ;-)
Um ungefĂ€hr zu bewerten, wo Sie das Element platzieren möchten, mĂŒssen Sie herausfinden, inwieweit es sich vom durchschnittlichen Element des Arrays unterscheidet. Dazu mĂŒssen Sie die Werte der minimalen und maximalen Elemente sowie die GrĂ¶ĂŸe des Arrays kennen.

Das sortierte Array soll wirklich zufÀllige Daten enthalten. Alle Erfinder dieses Verfahrens kommen zu der gleichen Formel:


k ist die ungefÀhre Stelle im Array, an der sich das Element A ( i ) befinden sollte
min , max - Werte der minimalen und maximalen Elemente in Array A
GrĂ¶ĂŸe - Die Anzahl der Elemente in Array A

Hier ist so eine allgemeine Idee. Mal sehen, in welchen Variationen dieser Algorithmus immer wieder geboren wurde.

Sorting King Solomon :: Solomon sortieren



Diese Methode (und ihr schöner Name) wurde vom Benutzer von V2008n vor ungefĂ€hr 5 Jahren vorgeschlagen. Alles hat seine Zeit, "die Zeit, um Steine ​​zu streuen und die Zeit, um Steine ​​zu sammeln" (die Worte von König Salomo aus dem Buch des Predigers) - und im Algorithmus passiert genau dies. ZunĂ€chst streuen wir mit Hilfe der Formel die Elemente an den gewĂŒnschten Stellen im Array. Da die Formel keine exakte, sondern eine ungefĂ€hre Position angibt, beanspruchen mehrere Elemente, deren Wert nahe beieinander liegt, einige Positionen gleichzeitig. Diese lokalen Elementgruppen werden nach EinfĂŒgungen sortiert und dann in der endgĂŒltigen Reihenfolge zusammengesetzt.

Interpolation sortieren


"Es gibt nichts Neues unter der Sonne", um den gleichen Autor noch einmal zu zitieren. Wikipedia beschreibt die Sortierung durch Interpolation, die verdĂ€chtig an die Sortierung nach Solomon erinnert. Jeder „Steinhaufen“ ist ein kleines zusĂ€tzliches dynamisches Array, in dem sich Elemente von Ă€hnlicher Bedeutung befinden. Der Hauptunterschied besteht darin, dass diese lokalen unsortierten Elementgruppen nach dem „Streuen von Steinen“ nicht nach EinfĂŒgungen sortiert werden, sondern sich selbst durch Interpolation (rekursiv oder in einer Schleife) sortieren.

Ein geordnetes Array ist ein diskreter Datensatz, der als endlicher Satz bekannter Werte einer bestimmten unbekannten Funktion betrachtet werden kann. Eigentlich eine ungefÀhre Verteilung aus Sicht der Rechenmathematik - das ist Interpolation.

JavaScript Interpolation Sort - 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); } } } } };

Sortierung der JavaScript-Interpolation - rekursive Version
 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];} } } };

Histogramm sortieren :: Histogramm sortieren


Dies ist eine Optimierung der Sortierung durch Interpolation, die die Anzahl der Elemente zĂ€hlt, die zu lokalen unsortierten Gruppen gehören. Mit dieser Anzahl können Sie unsortierte Elemente direkt in das resultierende Array einfĂŒgen (anstatt sie in separate kleine Arrays zu gruppieren).

JavaScript-Leiste Sortieren
 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];} } } };

Sortierung der Interpolations-Tags


Um den Overhead weiter zu optimieren, wird hier vorgeschlagen, sich nicht die Anzahl der Elemente von Àhnlicher Bedeutung in unsortierten Gruppen zu merken, sondern einfach den Anfang dieser Gruppen mit True / False-Flags zu markieren. True bedeutet, dass die Untergruppe bereits sortiert ist, und False bedeutet, dass dies noch nicht der Fall ist.

JavaScript-gekennzeichnete Interpolationssortierung
 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 };

Sortierung des Interpolations-Tags (an Ort und Stelle)


Wenn sich die Werte der Elemente im Array nicht wiederholen und gleichmĂ€ĂŸig verteilen (grob gesagt - wenn die Daten in sortierter Form eine Art arithmetischer Abfolge sind), können Sie in einem Durchgang sortieren, ohne die Elemente in Zwischenarrays zu verschieben.

Sortieren nach Interpolation mit (vorhandenen) Beschriftungen in 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; } } };

Flash Sort :: Flashsort


Ich schrieb einmal ĂŒber das Sortieren, das 1998 von Professor fĂŒr Biophysik Neubert erfunden wurde.

Der Professor schlug vor, die Elemente auf mehrere Klassen aufzuteilen (die Klassenzugehörigkeit wird durch die GrĂ¶ĂŸe des Elements bestimmt). In diesem Sinne sieht die Formel folgendermaßen aus:


Anstelle von Size (ArraygrĂ¶ĂŸe) gibt die Formel m an - die Anzahl der Klassen, nach denen wir die Elemente des Arrays verteilen. Die Formel berechnet nicht den SchlĂŒssel im Array, in den das Element geworfen werden soll, sondern die Klassennummer, zu der das Element gehört.

Diese Sortierung ist insofern nicht schlecht, als es um zusÀtzlichen Speicher sparsamer geht. Die Umverteilung der Elemente erfolgt an Ort und Stelle. Nur die Lokalisierung von Klassen wird separat gespeichert (aus einem anderen Blickwinkel wird die Anzahl der Elemente, die zu einer bestimmten Klasse gehören, separat gespeichert).

Nun, der Rest ist das gleiche Lied.


Flash-Sortierung in Java
 /** * 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(); } } }

UngefÀhre Sortierung :: Proxmap-Sortierung


Diese Sortierung ist die Ă€lteste der hier genannten und wurde 1980 von Professor Thomas Standish von der University of California eingefĂŒhrt. In der Erscheinung scheint es deutlich anders zu sein, aber wenn man genau hinschaut, ist alles gleich.

Der Algorithmus arbeitet mit einem solchen Konzept wie einem Treffer - einer bestimmten Zahl, deren Wert einem Element des Arrays nahe kommt.
Um festzustellen, ob ein Array-Element ein Treffer ist, wird eine NĂ€herungsfunktion auf das Element angewendet.

Professor Standish sortierte Arrays von reellen Zahlen. Die NĂ€herungsfunktion bestand darin, die reellen Zahlen auf eine ganze Zahl abzurunden.
Das heißt zum Beispiel, wenn das Array Elemente 2.8, 2, 2.1, 2.6 usw. enthĂ€lt. dann ist ein Treffer fĂŒr diese Nummern zweifellos.



Allgemeine Vorgehensweise:

  1. Wir wenden auf jedes Element eine Approximationsfunktion an, um zu bestimmen, welcher Treffer dem nÀchsten Element entspricht.
  2. Somit können wir fĂŒr jeden Treffer die Anzahl der Elemente berechnen, die diesem Treffer entsprechen.
  3. Wenn wir die Anzahl der Elemente fĂŒr alle Treffer kennen, bestimmen wir die Lokalisierung der Treffer (Rahmen links) im Array.
  4. In Kenntnis der Lokalisierung von Treffern bestimmen wir die Lokalisierung jedes Elements.
  5. Nachdem wir die Lokalisierung des Elements ermittelt haben, versuchen wir, es an seiner Stelle in das Array einzufĂŒgen. Wenn der Platz bereits vergeben ist, verschieben wir die Nachbarn nach rechts (wenn das Element kleiner ist als sie), um Platz fĂŒr das Element zu schaffen. Oder rechts fĂŒgen wir das Element selbst ein (wenn es mehr als Nachbarn sind).

Als NÀherungsfunktion können Sie eine beliebige Funktion basierend auf der allgemeinen Art der Daten im Array zuweisen. In modernen Implementierungen dieser Sortierung werden Treffer normalerweise nicht durch Knabbern des Bruchteils bestimmt, sondern unter Verwendung unserer Lieblingsformel.

Sortierung der JavaScript-Approximation
 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];} };

Sortieren nach EinfĂŒgung der Hash-Sortierung :: Hash-Sortierung


Nun, wir beenden unsere ÜberprĂŒfung mit dem Algorithmus , den der Habraiser bobbyKdas vor 6 Jahren vorgeschlagen hat. Dies ist ein hybrider Algorithmus, bei dem zusĂ€tzlich zur Verteilung und EinfĂŒgung auch die ZusammenfĂŒhrung hinzugefĂŒgt wird.

  1. Das Array wird rekursiv in zwei HĂ€lften geteilt, bis die GrĂ¶ĂŸe der Halb-Subarrays zu einem bestimmten Zeitpunkt die MindestgrĂ¶ĂŸe erreicht (der Autor hat nicht mehr als 500 Elemente).
  2. Auf der niedrigsten Rekursionsstufe wird auf jedes Halb-Subarray ein vertrauter Algorithmus angewendet. Unter Verwendung derselben Formel erfolgt eine ungefĂ€hre Verteilung innerhalb des Subarrays, wobei nach EinfĂŒgungen lokaler unsortierter Abschnitte sortiert wird.
  3. Nach der Anordnung der beiden HĂ€lften der Subarrays verschmelzen sie.
  4. Punkt 3 (ZusammenfĂŒhren sortierter HĂ€lften-Subarrays) wird wiederholt, wenn durch Rekursionsebenen nach oben geklettert wird, wenn das ursprĂŒngliche Array aus zwei HĂ€lften kombiniert wird.

Sortieren nach Hash-EinfĂŒgung in Java
 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(); } }

Die Formel selbst wird als Hash-Funktion bezeichnet, und das Hilfsarray fĂŒr die ungefĂ€hre Verteilung wird als Hash-Tabelle bezeichnet.

Referenzen


Interpolation & Histogramm , Flash , Proxmap

Solomon , Hash-Tabelle , Flash

Serienartikel:



Die AnnÀherungssortierung wurde in der AlgoLab Excel-Anwendung angezeigt (in diesem Fall wird der zufÀllige Bruchteil im anfÀnglichen unsortierten Array an Ganzzahlen angehÀngt). Solomon und Flash sind schon lange dabei, haben aber noch keine Interpolation, Hash und Histogramm implementiert.

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

More articles:


All Articles