Bibliothek sortieren

Nehmen Sie ein Array in umgekehrter Reihenfolge und sortieren Sie es mit einfachen Einfügungen .



Sehen Sie, mit welchem ​​Knarren das nächste Element an der richtigen Stelle eingefügt wird. Dafür müssen Sie die Einfügestelle freigeben, wodurch Sie alle zuvor eingefügten Elemente verschieben müssen.

Und wie gut wäre es, wenn zwischen den zuvor eingefügten Elementen Leerzeichen wären! Dann müsste man die Elementreihen nicht nur zum Einfügen ziehen.

Im Jahr 2004 beschlossen drei Informatik-Experten - Michael Bender, Martin Farah-Colton und Miguel Mostiro -, die Sortierung mit einfachen Einsätzen auf diese Weise zu ändern. Sie schlugen vor, einen geordneten Teil des Arrays zu bilden und Lücken zwischen den eingefügten Elementen zu lassen.

Der Bibliothekar muss die Bücher alphabetisch in einem langen Regal anordnen: Beginnend links vom Buchstaben „A“ stehen die Bücher direkt nebeneinander bis zum „Ich“. Wenn die Bibliothek ein neues Buch mit Bezug zu Abschnitt "B" erhalten hat, müssen Sie jedes Buch von der Mitte des Abschnitts "B" bis zum letzten "I" verschieben, um es an der richtigen Stelle ins Regal zu stellen. Dies ist das Sortieren nach einfachen Einfügungen. Wenn der Bibliothekar jedoch den freien Platz in jedem Abschnitt reservierte, genügte es ihm, nur wenige Bücher zu verschieben, um Platz für Buchneuheiten zu schaffen. Dies ist das Grundprinzip der Bibliothekssortierung.

Algorithmus

• 1. Erstellen Sie ein leeres Hilfsarray, das um ein Vielfaches größer ist als das Hauptarray.
• 2. Für das nächste Element suchen wir nach der Einfügungsstelle im Hilfsarray.
  • 2.1. Wenn Sie einen Platz zum Einfügen finden, übertragen Sie den Artikel und kehren Sie zu Schritt 2 zurück.
  • 2.2. Wenn kein Platz zum Einfügen vorhanden ist, gleichen Sie das Hilfsarray neu aus und kehren Sie zu Punkt 2 zurück.
• 3. Nachdem Sie alle Elemente verarbeitet haben, übertragen Sie sie zurück in das Hauptarray.

Auf den ersten Blick scheint das Sortieren einfach und unkompliziert zu sein. Um diese Illusion zu zerstreuen, betrachten wir die wichtigsten Punkte des Algorithmus genauer.

Größe des Zusatzarrays

Es gibt zwar keine etablierte Meinung, aber wie oft sollte das Hilfsarray größer sein als das Hauptarray.

Wenn Sie zu viel nehmen, ist zwischen den Elementen viel Platz. Die Suche nach der Einfügungsstelle und der Neuausgleich sind jedoch aufgrund der großen Abstände zwischen den Elementen langsamer. Rebalancing wird seltener vorkommen, aber sie müssen mehr Ressourcen für sie ausgeben. Wenn Sie zu wenig nehmen, ist das Suchen und Neuausgleichen billiger, aber Sie müssen das Array häufiger neu formatieren. Im Allgemeinen muss noch mit unterschiedlichen Werten getestet werden, und die Methode des wissenschaftlichen Stocherns bestimmt die beste Option.

Wenn wir entschieden haben, wie oft das Hilfsarray größer als das Hauptarray ist, sieht die Formel zur Bestimmung der genauen Anzahl der Elemente folgendermaßen aus:

NewSize = ε × (Größe + 1) - 1

NewSize - Die Anzahl der Elemente im Hilfsarray
ε - wie oft ist das Hilfsarray größer als das Hauptarray
Größe - Die Anzahl der Elemente im Hauptarray

Wenn wir die Größe einfach mit einem Faktor multiplizieren: NewSize = Size × ε , dann haben wir für eine gleichmäßige Verteilung nicht genügend Zellen in der Menge von ε - 1 Stück. Das heißt, es ist möglich, sie gleichmäßig anzuordnen, aber entweder die erste oder die letzte gefüllte Zelle befindet sich nahe dem Rand des Hilfsarrays. Und wir müssen die leeren Stellen in den gefüllten Zellen von allen Seiten reservieren - auch vor dem ersten und nach dem letzten Element.



Es scheint eine Kleinigkeit zu sein, aber in der Tat ist es wichtig, das Gleichgewicht wieder herzustellen, um freie Stellen zum Einfügen überall zu gewährleisten, auch bei der Verarbeitung der letzten Elemente des Hauptarrays.

Suchen Sie nach einem Einfügeplatz im Hilfsarray

Natürlich benötigen Sie hier eine binäre Suche. Die klassische Implementierung wird jedoch bei uns nicht funktionieren.

Erstens besteht das Hilfsarray hauptsächlich aus Hohlräumen. Wenn wir die Struktur rekursiv dichotomisieren, werden wir daher größtenteils auf ungefüllte Zellen stoßen. In diesen Fällen müssen Sie ein wenig nach links oder rechts zur nächsten nicht leeren Zelle gehen. Am Ende des Segments befinden sich dann wichtige Elemente, mit denen Sie das arithmetische Mittel berechnen und die binäre Suche eingehend fortsetzen können.

Zweitens vergessen Sie nicht die Kanten. Wenn Sie ein minimales oder maximales Element einfügen müssen, führt eine binäre Suche unter den zuvor eingefügten Elementen zu nichts. Daher lohnt es sich, Grenzfälle zu berücksichtigen. Überprüfen Sie zunächst, ob ein Element in der Nähe des linken oder rechten Randes des Arrays platziert werden muss, und verwenden Sie dann die binäre Suche, wenn dies nicht der Fall ist.

Drittens lohnt es sich unter Berücksichtigung der Besonderheiten des Antrags, zusätzliche Änderungen vorzunehmen, um die Anzahl der Array-Neuausrichtungen zu minimieren. Wenn das eingefügte Element dem Wert an einem der Enden des Segments entspricht, sollten Sie es möglicherweise nicht in der Mitte des Segments einfügen. Es ist logischer, neben ein Element zu stellen, dessen Wert diesem Wert entspricht. Dadurch wird der leere Raum des Hilfsarrays effizienter gefüllt.

Viertens, fünftens und so weiter. Die Qualität der Suche nach dem Einfügeort wirkt sich direkt auf die Sortiergeschwindigkeit aus, da die Auswahl nicht erfolgreicher Einfügungsorte zu einem unnötigen Neuausgleich führt. Zum Beispiel kann es sich lohnen, die Segmente nicht genau in der Mitte zu teilen, sondern näher am linken oder rechten Rand des Segments, je nachdem, an welcher Kante das Einfügeelement näher am Wert liegt.

Der binäre Suchalgorithmus selbst ist mit Fallstricken behaftet, und unter Berücksichtigung der oben genannten zusätzlichen Nuancen wird er schließlich keineswegs zu einer nicht trivialen Aufgabe.

Array-Neuausrichtung

Die binäre Suche ist bei dieser Sortierung nicht am schwierigsten zu implementieren. Es gibt immer noch ein Gleichgewicht.

Wenn kein Platz zum Einfügen vorhanden ist (ähnliche Elemente wurden gefunden, aber keine freien Zellen zwischen ihnen), müssen Sie das Hilfsarray schütteln, damit der Platz zum Einfügen freigegeben wird. Dieses Schütteln des Arrays gleicht das Gleichgewicht aus.

Darüber hinaus ist die Neuausrichtung lokal oder vollständig .

Lokale Neuausrichtung

Wir verschieben so viele Elemente wie nötig, um die Einfügemarke freizugeben. Die Implementierung eines solchen Ausgleichs ist sehr einfach. Sie müssen nur die nächste leere Zelle an der Einfügemarke ermitteln und damit mehrere Elemente verschieben.

Es gibt mögliche Nuancen. Wie kann man zum Beispiel nach dem nächsten freien Platz suchen? Um die Situation zu vermeiden, in der eine Verschiebung nicht möglich ist (dh wenn auf einer Seite alle Zellen bis zum äußersten Rand des Arrays belegt sind), können Sie sich auf die Position der Einfügemarke relativ zur Mitte des Arrays konzentrieren. Wenn Sie auf der linken Seite des Arrays einfügen müssen, wechseln Sie nach rechts, wenn rechts, nach links. Wenn ε ≥ 2 ist, beseitigt dieser Ansatz die Situation, in der eine Verschiebung unmöglich ist (weil in der Hälfte des Hilfsarrays mehr als genug Platz für alle Elemente vorhanden ist).

In der Interpretation des Algorithmus durch den Autor wird eine lokale Neuausrichtung impliziert.

Komplette Neuausrichtung

Eine interessante Alternative zu lokal ist die vollständige Neuausrichtung. Das heißt, im Hilfsarray werden alle verfügbaren Elemente so verschoben, dass zwischen ihnen (fast) die gleichen Leerzeichen liegen.



Ich habe beide Optionen ausprobiert und bis jetzt beobachte ich, dass der Algorithmus beim lokalen Neuausgleich 1,5 bis 2 Mal schneller funktioniert als bei der vollständigen. Eine vollständige Neuausrichtung kann jedoch weiterhin hilfreich sein. Wenn Sie beispielsweise zu oft lokal neu ausgleichen müssen, bedeutet dies, dass sich in einigen Bereichen im Array viele „Blutgerinnsel“ angesammelt haben, die den gesamten Prozess hemmen. Eine einmal durchgeführte vollständige Neuausrichtung ermöglicht es Ihnen, alle lokalen Überlastungen auf einen Schlag zu beseitigen.

Lassen Sie uns herausfinden, wie Sie das Gleichgewicht wieder vollständig herstellen können.

Zuerst müssen Sie berechnen, wie viele maximale Zellen wir jedem Element im Hilfsarray zuordnen können. Es ist zu beachten, dass leere Zellen sowohl vor als auch nach der letzten gefüllten Zelle stehen müssen. Die Formel lautet:



M - die Anzahl der Zellen, die jedem Element zugewiesen werden können
NewSize - Größe des Hilfsarrays
Count - Die aktuelle Anzahl nicht leerer Elemente im Hilfsarray

Dieser Bruch muss auf einen ganzzahligen Wert reduziert (dh abgerundet) werden. Aus der Formel geht hervor, dass je mehr Elemente bereits auf das Hilfsarray übertragen werden, desto weniger Zellen können wir für die Nachbarschaft jedes Elements auswählen.

Wenn wir M kennen , erhalten wir leicht die genaue Position für jedes nicht leere Element in dem Hilfsarray, auf dem es sich befinden soll, nachdem der Neuausgleich abgeschlossen ist.

NewPos = Anzahl × M.

NewPos - neue Artikelposition nach dem Ausgleich
Zahl - Was ist das nicht leere Element im Hilfsarray (1 ≤ Zahl ≤ Anzahl)?
M - die Anzahl der Zellen, die jedem Element zugeordnet sind

Neue Positionen sind bekannt. Können Sie nicht leere Elemente im Hilfsarray einfach aussortieren und an andere Stellen übertragen? Oh nein, beeil dich nicht. Es ist nicht nur notwendig, Elemente zu übertragen, es ist auch wichtig, ihre Reihenfolge aufrechtzuerhalten. Und als Ergebnis der binären Suche und Einfügung können sich Elemente als viel links und viel rechts von der Position herausstellen, an der sie sich nach dem Neuausgleich befinden sollten. Und an dem Ort, an dem Sie umziehen möchten, gibt es möglicherweise ein anderes Element, das ebenfalls irgendwo angebracht werden muss. Außerdem können Sie ein Element nicht übertragen, wenn sich zwischen seiner alten und der neuen Position im Hilfsarray andere Elemente befinden. Andernfalls werden die Elemente verwechselt, und es ist äußerst wichtig, dass wir die Reihenfolge nicht verwechseln.

Um das Gleichgewicht wieder herzustellen, reicht es daher nicht aus, den üblichen Zyklus zu durchlaufen und einfach jedes Element von einer Tasche in eine andere zu verschieben. Es ist weiterhin erforderlich, die Rekursion zu verwenden. Wenn ein Element nicht an einen neuen Ort verschoben werden kann (andere Elemente wurden zwischen seiner alten und seiner neuen Position angezeigt), müssen Sie zuerst diese ungebetenen Gäste (rekursiv) herausfinden. Und dann wird alles richtig angeordnet.

Entarteter Fall

Für die meisten Sortierungen nach Einfügungen ist ein Array in umgekehrter Reihenfolge die schlechteste Situation. Und das Sortieren eines Bibliothekars ist leider keine Ausnahme.



Elemente tendieren zum linken Rand des Hilfsarrays, wodurch die leeren Stellen schnell ausgehen. Sie müssen das Array sehr oft neu ausbalancieren.

Übrigens, wenn wir ein fast geordnetes Array nehmen (der beste Fall für das Sortieren nach einfachen Einfügungen), dann bekommen wir das gleiche Problem. Neu ankommende Elemente verstopfen nicht die linke, sondern die rechte Seite des Hilfsarrays, was ebenfalls zu einem zu häufigen Neuausgleich führt.

Die Bibliothekssortierung verarbeitet zufällige Datensätze effizient. Teilbestellungen (sowohl direkt als auch rückwärts) beeinträchtigen die Geschwindigkeitsleistung.

Algorithmische Komplexität

Bei großen Mengen zufälliger Daten gibt der Algorithmus die Zeitkomplexität O ( n log n ) an. Gar nicht schlecht!

Bei Sätzen zufälliger eindeutiger (oder größtenteils eindeutiger) Daten mit der richtigen Auswahl des Koeffizienten ε und der erfolgreichen Implementierung der binären Suche kann die Anzahl der Neuausgleiche minimiert oder sogar vermieden werden. Es kann argumentiert werden, dass der Algorithmus die beste Zeitkomplexität O ( n ) aufweist.

Ein großer Prozentsatz von Daten, die sich im Wert wiederholen, sowie das Vorhandensein geordneter (in direkter oder umgekehrter Reihenfolge) Teilsequenzen im Array führen zu einem häufigen Neuausgleich des Hilfsarrays und in den ungünstigsten Fällen zu einer Verschlechterung der Zeitkomplexität auf O (n ² ).

Das Minus des Algorithmus ist natürlich, dass das Hilfsarray O ( n ) zusätzlichen Speicher benötigt.

Mögliche Verbesserungsmöglichkeiten

Obwohl der Algorithmus selbst bei zufälligen Daten lehrreich und effizient ist, haben in anderthalb Jahrzehnten nur wenige Interesse daran gezeigt.

Wenn Sie auf die Anfrage "Bibliothekssortierung" googeln, finden Sie einen flüchtigen Artikel in der englischen Wikipedia, das PDF des Autors (von dem wenig verstanden wird) und eine seltene Neuveröffentlichung dieser mageren Informationen. Außerdem gibt es eine gute Visualisierung in YouTube, wo die Haupt- und Hilfsarrays ursprünglich kombiniert wurden. Alle Links befinden sich am Ende des Artikels.

Die Suche nach „Bibliothekssortierung“ macht noch mehr Spaß - im Beispiel finden Sie die verschiedenen Sortierungen, die in verschiedenen Bibliotheken enthalten sind. Diese Algorithmen beziehen sich jedoch nicht auf die authentische Bibliothekssortierung .

Und es gibt etwas zu verbessern:

1. Empirische Auswahl des optimalen Koeffizienten ε .
2. Änderung (unter Berücksichtigung der Besonderheiten des allgemeinen Algorithmus) der binären Suche zur effizientesten Bestimmung der Einfügemarke.
3. Minimierung der Ausgleichskosten.

Wenn Sie diese Stellen polieren, entspricht die Sortierung der Bibliothek in der Geschwindigkeit möglicherweise sogar der schnellen Sortierung?

Quellcode

Ich habe es nicht geschafft, die Implementierung in Python vorzubereiten, es gibt eine funktionierende Version in PHP.








Ich musste selbst von Grund auf neu programmieren, basierend auf einer allgemeinen Beschreibung der Methode. Ich habe keine Geschwindigkeit gesehen, die der schnellen Sortierung nahe kommt. Meine Bibliothekssortieroption sortiert 10 bis 20 Mal langsamer als die schnelle Sortierung. Aber der Grund ist natürlich, dass meine Implementierung zu grob ist, vieles wurde nicht berücksichtigt.

Ich würde gerne eine Version von den Machern des Algorithmus sehen. Ich werde heute an die Autoren schreiben (und ihnen einen Link zu diesem Habrastatu geben), sie werden plötzlich antworten. Obwohl ... ich erinnere mich, ich habe versucht, Allen Beachich ( ABC-Sortierung ) und Jason Morrison ( J-Sortierung ) zu kontaktieren, aber das Ergebnis war das gleiche, als hätte ich in Sportloto geschrieben.

UPD Martin Farah-Colton antwortete mir, dass sie die Implementierung nie durchgeführt hätten:

Ich fürchte, wir haben diese Algorithmen nie implementiert.

Die Hauptsache ist die Idee :)

Algorithmusmerkmale

Referenzen

Bibliothek sortieren

Visualisierung des Bibliothekssortieralgorithmus

Die Einfügesortierung ist O (n log n).

Autoren des Algorithmus:

Michael A. Bender
Martin Farah-Colton
Miguel Mostiro

Serienartikel:

• Excel-Anwendung AlgoLab.xlsm
• Sorte austauschen
• Insertion Sorts
  • Bibliothekar Sort
  • Solitaire Sort
  • Sortieren Sie "Turm von Hanoi"
  • Junge Tischsortierung
  • Sortierung umkehren
  • Sortiervergleich einfügen
• Nach Auswahl sortieren
• Sortierungen zusammenführen
• Nach Verteilung sortieren
• Hybridsortierung

Sortierung zu AlgoLab hinzugefügt. So können Sie mit kleinen Datenmengen experimentieren.

In diesem Fall können Sie entscheiden, wie oft das Hilfsarray größer als das Hauptarray ist. Um den Koeffizienten ε auszuwählen , können Sie mit der rechten Maustaste auf die Zelle mit „Bibliothekssortierung“ klicken und „Notiz ändern“ auswählen. Stellen Sie in der Notiz den ganzzahligen Wert für e sorgfältig von 2 auf 5 ein. Wenn Sie anstelle dieser Zahlen etwas anderes eingeben, wird der Standardwert = 2 verwendet.

Sie können auch die Art der Neuausrichtung auswählen. Wenn Sie local = 1 setzen, wird die lokale Neuausrichtung verwendet. Wenn lokal = 0 - voll.

Vergessen Sie nicht, vor Beginn der Visualisierung den optimalen Maßstab für das Prozessblatt festzulegen, da sonst das Hilfsarray nicht auf den Bildschirm passt.