Überprüfung und Erprobung von Sortiermethoden. Teil I

Neulich hatte ich in den Kommentaren auf VKontakte einen Streit mit einem der anderen Studenten des Projekts. Der Kern des Streits war „Wer wird gewinnen“ – eine Methode sort()aus einer Klasse java.util.Arraysoder selbst geschriebene Implementierungen einfacher Algorithmen: Blase , Einfügung , Auswahl , Shell (Shell-Algorithmus). Für einige mag die Antwort auf diese Frage offensichtlich sein, aber da der Streit entstand, obwohl jede Seite über „angesehene Quellen“ verfügte, die ihren Standpunkt unterstützten, wurde beschlossen, eine Studie durchzuführen, um die grauen Zellen zu erweitern den Prozess und implementiert verschiedene Algorithmen. TL;DR: java.util.Arrays.sort() Bei Arrays mit 100.000 Elementen oder mehr ist sie bedingungslos führend; bei einer kleineren Größe kann die Shell-Methode manchmal mit ihr konkurrieren. Die übrigen betrachteten Algorithmen sind völlig leer und können nur unter einigen exotischen Bedingungen nützlich sein. Schauen wir uns nun an, wie Arrays in unseren Silizium-Übergeräten sortiert sind.

Auswahlsortierung. Sortierung nach Auswahl

Beginnen wir mit der einfachsten und offensichtlichsten Methode. Das Wesentliche davon wird uns von Robert Sedgwick in seinem Videovortrag auf Coursera perfekt demonstriert (ich zitiere die Animation von dort, die ich schlecht in ein GIF komprimiert habe): Ansicht Durchlaufen des Arrays vom ersten Element an, bei jedem Schritt wir Suchen Sie auf der rechten Seite nach dem minimalen Element, mit dem wir das aktuelle austauschen. Daher behalten wir uns die endgültige Version unseres Arrays in sortierter Form vor. Hier ist der Code, der diesen Algorithmus in Java implementiert:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

Die Analyse des Algorithmus zeigt, dass es notwendig ist, den Rest des Arrays bei jedem Durchgang zu durchkämmen, das heißt, wir benötigen genau N + (N-1) + (N-2) + ... + 1 = N^ 2/2 Vergleiche. Somit beträgt die Komplexität des Algorithmus O(N^2). Was bedeutet das? Das bedeutet, dass wir durch die Erhöhung der Anzahl der Elemente im Array (N) um das Zweifache die Laufzeit des Algorithmus nicht um das Zweifache, sondern um das 2^2 = Vierfache erhöhen. Indem wir N um das Zehnfache erhöhen, erhöhen wir die Betriebszeit um das Hundertfache und so weiter. Auf meinem 2012er Laptop mit einem Core i3-Prozessor unter Ubuntu 14.4 habe ich die folgende Betriebszeit erreicht:

Sortieren durch Einfügen. Sortieren durch Einfügen

Hier ist die Idee etwas anders. Wenden wir uns noch einmal der Animation von Doktor Sedgwick zu: „ Sehen Sie , was vor uns liegt“, haben wir noch nicht einmal gesehen, und alles, was wir zurücklassen, bleibt immer in Ordnung. Der Punkt ist, dass wir jedes neue Element des ursprünglichen Arrays an den Anfang „zurückbringen“, bis es auf einem kleineren Element „ruht“. Somit haben wir wieder N Durchgänge (für jedes Element des ursprünglichen Arrays), aber in jedem Durchgang betrachten wir in den meisten Fällen nicht den gesamten Rest, sondern nur einen Teil. Das heißt, wir erhalten die Option 1 + (N-1) + (N-2) + … + N = N^2/2 nur dann, wenn wir jedes nächste Element ganz an den Anfang zurücksetzen müssen, also in den Fall der Eingabe „in umgekehrter Reihenfolge“ sortiert (Pech, Pech). Im Falle eines bereits sortierten Arrays (hier ist Glück) gibt es ein komplettes Gratisangebot – bei jedem Durchgang erfolgt nur ein Vergleich und das Belassen des Elements an Ort und Stelle, das heißt, der Algorithmus arbeitet in einer Zeit, die proportional zu N ist. Die Komplexität des Algorithmus wird durch den schlechtesten theoretischen Fall bestimmt, d. h. O( N^2). Im Durchschnitt ist die Betriebszeit proportional zu N^2/4, also doppelt so schnell wie beim vorherigen Algorithmus. In meiner Implementierung war die Laufzeit aufgrund der nicht optimalen Verwendung der Permutation länger als die von Selection. Ich habe vor, den Beitrag bald zu korrigieren und zu aktualisieren. Hier ist der Code und das Ergebnis seiner Operation auf derselben Maschine:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Muschelsortierung. Muschelsortierung

Ein schlauer Kerl, Donald Schell, bemerkte bereits 1959, dass die teuersten Fälle im Einfügungsalgorithmus dann auftreten, wenn das Element sehr weit an den Anfang des Arrays zurückkehrt: Bei einem Durchlauf bringen wir das Element um einige Positionen an den Anfang zurück , und bei einem weiteren Durchgang ist es weit und lang, fast durch die gesamte Reihe bis zum Anfang. Ist es möglich, dies auf einmal zu tun und dabei durch mehrere Elemente zu springen? Und er hat einen solchen Weg gefunden. Es besteht darin, nacheinander spezielle Teilsortierungen durchzuführen, die im Allgemeinen als D-Sortierung oder, nach Sedgwick, als H-Sortierung bezeichnet werden (ich vermute, dass „h“ „Sprung“ bedeutet). Die 3-Sortierung vergleicht beispielsweise das betreffende Element nicht mit dem vorherigen, sondern überspringt zwei und vergleicht mit dem drei Positionen zurückliegenden Element. Bei einer Änderung wird es erneut mit dem Element um 3 Positionen zurück verglichen und so weiter. Die Quintessenz ist, dass das resultierende Array „3-sortiert“ ist, d. h. die falsche Position der Elemente beträgt weniger als 3 Positionen. Die Arbeit mit diesem Einfügealgorithmus wird einfach und angenehm sein. „1-Sort“ ist übrigens nichts anderes als nur ein Einfügungsalgorithmus =) Durch sequentielles Anwenden von h-sort auf das Array mit abnehmenden h-Werten können wir ein großes Array schneller sortieren. So sieht es aus: Ansicht Die Herausforderung besteht darin, die richtige Reihenfolge der Teilsortierungen auszuwählen. Letztlich hängt davon die Leistungsfähigkeit des Algorithmus ab. Am gebräuchlichsten ist die von Donald Knuth vorgeschlagene Reihenfolge: h = h*3 + 1, also 1, 4, 13, 40, ... und so weiter bis zu 1/3 der Array-Größe. Diese Reihenfolge bietet eine ordentliche Leistung und ist zudem einfach zu implementieren. Die Analyse des Algorithmus erfordert eine Menge Sprache und übersteigt meine Fähigkeiten. Die Breite der Analyse wird auch durch die vielen Varianten der h-Sequenzen bestimmt. Empirisch können wir sagen, dass die Geschwindigkeit des Algorithmus sehr gut ist – überzeugen Sie sich selbst: Eine Million Elemente in weniger als einer Sekunde! Und hier ist der Java-Code mit der Knut-Sequenz.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Blasensortierung. Blasenmethode

Das ist ein Klassiker! Fast jeder unerfahrene Programmierer implementiert diesen Algorithmus. Es ist so ein Klassiker, dass Dr. Sedgwick nicht einmal eine Animation dafür hatte, also musste ich die Arbeit selbst machen. Hier durchlaufen wir bei jedem Durchgang das Array vom Anfang bis zum Ende und tauschen benachbarte Elemente aus, die nicht in der richtigen Reihenfolge sind. Dadurch „schweben“ die größten Elemente (daher der Name) bis zum Ende des Arrays. Wir beginnen jeden neuen Durchgang optimistisch in der Hoffnung, dass das Array bereits sortiert ist ( sorted = true). Wenn wir am Ende des Abschnitts feststellen, dass wir einen Fehler gemacht haben, beginnen wir mit einem neuen Abschnitt. Die Schwierigkeit besteht darin, dass wir wiederum bei jedem Durchgang (fast) das gesamte Array durchlaufen. Der Vergleich findet bei jedem Schritt statt, der Austausch findet bei fast jedem Schritt statt, was diesen Algorithmus zu einem der langsamsten macht (wenn wir rational implementierte berücksichtigen und nicht „Shaking Sort“ und ähnliches). Interessant ist, dass die Komplexität hier formal ebenfalls gleich O(N^2) ist, der Koeffizient jedoch viel höher ist als der von Einfügungen und Auswahlen. Algorithmuscode:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Betriebszeit: Spüren Sie den Unterschied: mehr als eine halbe Stunde bei einer Million Elementen! Fazit: Benutzen Sie diesen Algorithmus niemals!!!

Zusammenfassung des ersten Teils

Daher schlage ich vor, einen Blick auf die allgemeine Tabelle dieser Algorithmen zu werfen. Sie können auch mit den Ergebnissen der integrierten Methode vergleichen java.util.Arrays.sort(). Es sieht aus wie eine Art Magie – was könnte schneller sein als Shell? Darüber werde ich im nächsten Teil schreiben. Dort werden wir uns die weit verbreiteten Schnellsortierungsalgorithmen sowie die Zusammenführungssortierung ansehen, den Unterschied in den Methoden zum Sortieren von Arrays aus Grundelementen und Referenztypen kennenlernen und uns auch mit einer in dieser Angelegenheit sehr wichtigen Schnittstelle vertraut machen ; Comparable) Unten können Sie lernen ein Diagramm, das auf einer logarithmischen Skala unter Verwendung von Datentabellen erstellt wurde. Je flacher die Linie, desto besser der Algorithmus =) Für diejenigen, die das gesamte Projekt herunterladen und Tests selbst durchführen möchten, behalten Sie den Link: Java. Wir sehen uns im nächsten Teil! =)