Laden Sie AlgoLab von einem Google-Laufwerk herunter ( AlgoLab (Excel 2007-2013) .xlsm- und AlgoLab (Excel 97-2003) .xls-Dateien ).

Worüber die Bolschewiki so lange gesprochen haben und was ich seit mehreren Jahren in einem anderen Tempo verfolge, ist endlich passiert. Vor einigen Jahren schrieb er ein kleines Makro, um algorithmische GIF-Animationen für Habrastaty zu erstellen. Im Laufe der Zeit ist mein bescheidenes Instrument zu einer beeindruckenden Größe gewachsen, was jetzt keine Schande ist, der Welt zu offenbaren.

Also treffe dich.

AlgoLab ist eine Excel-Anwendung (dh eine Excel-Datei mit Makros), in der Sie sich Schritt für Schritt mit Sortieralgorithmen vertraut machen können. Außerdem besteht die Möglichkeit, GIF-Animationen vorzubereiten.



Nur 4 Blätter - 2 Haupt- und 2 so, informativ. Hier sind sie:_{Durch Klicken auf ein Bild wird ein Bild in voller Größe geöffnet}

• Blatt sortieren. Auf diesem Blatt können Sie schnell ein Array bilden und einen Sortieralgorithmus auswählen.
• Blattprozess. Hier beobachten wir Schritt für Schritt, wie dieser oder jener Algorithmus funktioniert.
• Blatt sortieren. Hier ist eine Zusammenfassung der Algorithmen.
• Blattdiagramm. Es gibt auch einen geplanten Veröffentlichungsplan für Artikel zum Sortieren.

Lassen Sie uns diese Blätter genauer kennenlernen.

Blatt sortieren

Der obere Teil des Blattes ist der Erzeugung eines unsortierten Arrays (damit der Algorithmus mit etwas versorgt werden kann) sowie dem Speichern der Visualisierung in Form von Bildern auf Ihrem Computer gewidmet:



In der allerersten Zeile befindet sich das Array selbst. Bei Bedarf können Sie die Werte einzelner Elemente manuell ändern:



Oben links müssen Sie die Hauptmerkmale für das generierte Array angeben:


Die Größe, ob sich die Werte im Array nicht wiederholen sollen (0 - nein, 1 - ja), die den minimalen und maximalen Elementen im Array entsprechen. VBA-Makros enthalten Vandalismusresistenz gegen Eingabedaten, sodass Sie einige falsche Werte eingeben können. In diesem Fall bestimmt die Anwendung, was diesem oder jenem Merkmal entsprechen soll.

Und auch eine Option, um zu bestimmen, ob der Algorithmus Schritt für Schritt ausgeführt werden muss (= 1) oder ob es möglich ist, die Struktur zu sortieren und nur das Endergebnis anzuzeigen (= 0). Natürlich wurde die Excel-Anwendung selbst erstellt, um den gesamten Prozess Schritt für Schritt zu beobachten. Daher ist der Wert hier normalerweise gleich eins. Aber manchmal mache ich beim Testen diese Option ungültig, um nur zu überprüfen, ob der neue Algorithmus, den ich zu AlgoLab.xlsm hinzufüge, überhaupt funktioniert (dh ich muss zuerst prüfen, ob das sortierte Array das Endergebnis ist, ohne Zeit mit dem Anzeigen der Visualisierung zu verschwenden )

Ein wenig rechts befindet sich der Bereich, in dem Sie angeben können, wie genau die Elemente im generierten unsortierten Array nicht sortiert sind.


Zufällig gemischtes Array generieren? Oder vielleicht die Elemente in absteigender Reihenfolge anordnen? Oder machen Sie das Array fast sortiert (und geben Sie auch den Koeffizienten für die fast Sortierung an)?

Um eine dieser Methoden auszuwählen, müssen Sie nur auf die Zelle mit dem Element klicken. Infolgedessen wird das Array in der ersten Zeile neu generiert. Die ausgewählte Zelle wird blau.

Auf der linken Seite befindet sich das Gebiet, das benötigt wird, wenn Sie nicht nur die Visualisierung bewundern, sondern auch den gesamten Prozess Frame für Frame als Bilder speichern möchten.


Zunächst müssen Sie angeben, ob die Sortierschritte im Allgemeinen in Bilder exportiert werden sollen (= 0, wenn nicht, = 1, wenn ja, und diese Option ist "einmalig", dh sie wird nach Abschluss der Sortierung auf Null zurückgesetzt). Zweitens müssen Sie das Bildformat angeben (nur 4 Optionen sind möglich: GIF, JPG, PNG und BMP. Die letzte Option liefert das Ergebnis mit der höchsten Qualität, daher empfehle ich es). Drittens müssen Sie den Pfad zu dem Ordner angeben, in dem die Bilder gespeichert werden sollen (klicken Sie auf diese Zelle, um ein Dialogfeld zur Auswahl eines Verzeichnisses zu öffnen). Dann kommt die Zelle, die das Makro selbst ausfüllt - die Sitzungskennung (erforderlich für den eindeutigen Namen des Unterordners, um Frames dieser bestimmten Sortieranwendung zu speichern). Außerdem muss der Erfassungsbereich korrekt angegeben werden (Koordinaten der oberen linken und unteren rechten Zelle, es sind die Frames, die auf sie beschränkt sind - nicht das gesamte Blatt kopieren?)


Nun, ganz rechts finden Sie die Zelle "Sortieren" (die als Schaltfläche zum Starten des Prozesses dient. Wenn Sie das Sortieren und Generieren eines Arrays auswählen, klicken Sie einfach darauf).

Auch neben dieser Schaltfläche leben verschiedene Sonderzeichen, die in der Visualisierung verwendet werden können. Diese Zellen müssen nicht berührt werden.

Am wichtigsten ist die Wahl des Algorithmus. Sie müssen nur auf den Namen der Sorte klicken, danach wird die Zelle mit ihr blau.



Von den mehr als 80 Algorithmen ist heute etwa die Hälfte verfügbar. Bisher haben nicht realisierte ein blasses Aussehen im Vergleich zu bereits implementierten. Ich habe es immer noch nicht geschafft (und noch nicht einmal mit der Implementierung begonnen). Einige sind in der Entwicklung. Einige von ihnen sind geschrieben und getestet und werden in Kürze verfügbar sein (insbesondere sind fast alle Sortierungen nach Beilagen für mich bereit. Ich werde sie jedoch der Anwendung hinzufügen, sobald in den kommenden Wochen Habrastate für diese Sortierungen freigegeben werden, und die aktualisierte AlgoLab.xlsm - und was zu tun ist, ich möchte keine neuen Folgen meiner Serie verderben).

Ich plane, einige der bereits implementierten Sortierungen zu ändern. Visualisierung befriedigt mich nicht überall.


In diesem Bereich werden jedoch bei der Auswahl eines Algorithmus zusammenfassende Informationen darüber geladen. Informationen werden aus dem Blatt "Sortieren" entnommen und automatisch mit einem Makro zurückgezogen. Wenn Sie den Text in diesem Bereich ändern, ändert sich dies übrigens auch auf dem Originalblatt.

Sortieren, wie Sie viel sehen können. Um in all dieser Pracht nicht verwirrt zu werden, werden sie in Klassen unterteilt, je nachdem, welche grundlegende Methode zum Organisieren von Daten verwendet wird. Was sind diese Klassen?

• Zufällige Sortierung. Die Elemente des Arrays werden zufällig gemischt und dies wird fortgesetzt, bis die Struktur plötzlich geordnet ist.
  
• Sortiert den Austausch. Ein vollständiger paarweiser Vergleich (und Austausch) von Array-Elementen wird organisiert.
• Beilagen sortieren. Elemente werden ausgewählt und jedes wird an seiner Stelle eingefügt.
• Nach Wahl sortieren. Im Subarray wird das maximale Element ausgewählt, das am Ende des Subarrays eingefügt wird. Dann wird zum verbleibenden unsortierten Teil der gleiche Vorgang wiederholt.
• Sortierungen zusammenführen. Durchsuchte geordnete Subarrays, die miteinander verbunden sind.
• Nach Verteilung sortieren. Elemente werden in Klassen unterteilt, bis dies zum gewünschten Ergebnis führt.
• Hybridsortierung. Die Methoden zum Austauschen, Einfügen, Auswählen, Zusammenführen und Verteilen von Algorithmen werden kombiniert.
• Parallele Sortierung. Algorithmen, bei denen verschiedene Teile des Arrays parallel verarbeitet werden.
• Netzwerke sortieren. Das Array wird durch das Sortiernetzwerk geleitet und am Ausgang geordnet.
• Andere Sortierungen. Pseudo-Algorithmen, komische und einfach extravagante Sortierungen.

In den kommenden Harastings werden detaillierte Nuancen für jede Klasse hervorgehoben. Nun, wir fahren mit dem nächsten Blatt fort.

Prozessblatt

Wenn Sie ein Array generieren, einen Algorithmus auswählen und auf die Schaltfläche "Sortieren" klicken, wird das Makro auf dieses Blatt geworfen. Hier liegt das Geheimnis der Datenorganisation.



Während des gesamten obigen Prozesses werden Sie von diesem wunderbaren Fenster begleitet:



Da der Anzeigemodus Schritt für Schritt erfolgt, müssen Sie die Taste „Neuer Schritt“ drücken , um mit dem nächsten Schritt fortzufahren. Es ist nicht sehr praktisch, dies mit der Maus zu tun, daher liegt der Fokus der Fenstereingabe immer auf dieser Schaltfläche. Das heißt, um mit den nächsten Schritten fortzufahren, müssen Sie nicht faul sein, um die Eingabetastatur zu drücken (es sind keine weiteren Gesten erforderlich).

Die Schaltfläche „Fertig stellen“ zeigt den Vorgang Schritt für Schritt an. Der Algorithmus schließt seine Arbeit stillschweigend ab und zeigt nur das Endergebnis an. Sie sehen nicht die letzte Phase des Sortiervorgangs.

Die Schaltfläche „Abbrechen“ stoppt die Arbeit von Makros in diesem Schritt vollständig.

Mit der Schaltfläche „Schnappschuss“ können Sie einen Screenshot dieses bestimmten Schritts speichern. Sie finden das Bild dann in dem Ordner, der in den Einstellungen auf dem Sortierblatt angegeben ist.

Blatt sortieren

Hier ist ein riesiger Tisch mit allerlei Wissen über Sorten gespeichert. Wie Sie sich erinnern, werden Informationen von hier abgerufen, wenn Sie die Sortierung auf dem Sortierblatt auswählen. Ich bereue, obwohl die Füllqualität mittelmäßig ist, gab es nicht genug Ausdauer, um die maximale Menge an korrekten Daten sorgfältig einzuführen. Ich hoffe, in naher Zukunft aufholen zu können.

Blattdiagramm

Auf diesem Blatt können Sie meine Fantasien über die Daten der nächsten habrastatischen Veröffentlichungen über Sorten kennenlernen.



Ich werde über Algorithmen in dieser Reihenfolge sprechen.

Börsen → Einfügungen → Auswahl → Zusammenführen → Verteilung →
→ Hybriden → Parallel → Netzwerk → Zufällig

Die allgemeinen Klassen sind aufgelistet, aber im Allgemeinen werden jeder Klasse mehrere Opusse gewidmet, die einem solchen allgemeinen Schema folgen.

1. Beschreibung der Sortierklasse. Einführende, grundlegende Nuancen, die allen Klassensorten innewohnen, grundlegende Klassensorten. In der Regel enthalten diese einführenden Artikel ziemlich bekannte Informationen. Trotzdem werde ich versuchen, mich nicht zu langweilen.
2. Einige wenig bekannte Klassensorten. Hier werde ich Sie mit neuem Material begeistern, über das es auf Russisch praktisch keine Informationen gibt. Und Sie werden auch auf Englisch nichts finden. In separaten Artikeln geht es nicht nur um das Sortieren von Börsen, da für ein interessantes Exklusiv lange keine Zeit blieb.
3. Praktischer Vergleich von Klassensorten untereinander. Für jede Gruppe von Algorithmen gibt es einen abschließenden Artikel zum Testen von Sortierungen in verschiedenen Datensätzen. Hier verspreche ich viele erstaunliche Entdeckungen!

Praktischer Sortiervergleich

Es war geplant, nur die Python-Implementierung von Algorithmen zu vergleichen. Nachdem ich jedoch die ersten Ergebnisse am Beispiel der Gnomsortierung gesehen hatte, kam ich zu dem Schluss, dass sie ein Missverständnis über die relative Geschwindigkeit vermitteln.

Python verfügt über ein eigenes System für den Zugriff auf den Speicher von Variablen (insbesondere wenn diese Variablen einander zugewiesen sind), weshalb optimierte Algorithmen langsamer ausgeführt werden können.



Eine ähnliche Situation mit Shaker / Bubble. Entgegen den Erwartungen funktioniert die Blasensortierung schneller als die Shaker-Sortierung (obwohl Shaker Sort eine verbesserte Blasensortierung ist).

Zur Kontrolle habe ich Sortierungen auch in PHP getestet (ich arbeite hauptsächlich in dieser Sprache, daher war ein alternativer Test schneller und einfacher zu erstellen). Dort ist die Situation bereits „normal“ - der optimierte „Gnom“ für alle Datensätze arbeitet deutlich schneller als normal.

PHP hat jedoch auch den Ruf, "unvollkommen" und ein langsames Werkzeug zu sein, weshalb ich entschied, dass es nicht für globale Schlussfolgerungen geeignet ist. Um mögliche Vorwürfe zu minimieren [bei der Auswahl der falschen Sprache zum Testen der tatsächlichen Geschwindigkeit], habe ich beschlossen, die Haupttests auch in Java zu minimieren. Ich hatte jedoch einen Mangel an Kenntnissen für diese Sprache. Leider ist es nicht zusammengewachsen.

Somit werden die Tests sofort in drei zwei Sprachen durchgeführt:

• Python Erstens eignet sich diese Sprache am besten zur Beschreibung des Algorithmus. Da die Funktionen korrekt funktionieren, messen wir die Zeit für sie. Die Ergebnisse werden jedoch etwas zweifelhaft sein.
• PHP Anfangs wollte ich diese Sprache in einer Reihe von Artikeln in keiner Weise verwenden. Aber da ich eine Umgebung zum Testen von Sortierungen geschrieben habe und die Implementierungen selbst auf diesem PL verfügbar sind, warum nicht? Praktische Ergebnisse, anhand derer man die relative Wirksamkeit von Algorithmen beurteilen kann, sind im Vergleich zu Python angemessener.
• Java Basierend auf den Ergebnissen in Java werden wir die wichtigsten Schlussfolgerungen ziehen.

Natürlich werden alle Optionen in allen Sprachen geteilt.

FAQ

Ich sehe bereits einige Fragen des Publikums voraus, die ich sofort beantworten werde.

Warum ist das Programm zur Visualisierung von Algorithmen in Excel implementiert?

Also war es einmal schneller und einfacher (für mich). Der Gitterraum von Tabellenkalkulationen erwies sich als sehr, sehr bequeme schlüsselfertige Lösung für die Visualisierung der Arbeit mit Arrays.

Ok, schauen wir uns all diese Arten an. Was weiter?

Basierend auf AlgoLab werde ich Visualisierungen für Bäume und Grafiken erstellen. Ulams Tischdecke, Langtons Ameise, das ist alles. Es gibt noch Leerzeichen für 2048 (KI spielt mit der Minimax- und Monte-Carlo-Methode - Sie müssen es beenden). Werke sind viel Land.

Referenzen

Laden Sie AlgoLab von einem Google-Laufwerk herunter ( AlgoLab (Excel 2007-2013) .xlsm- und AlgoLab (Excel 97-2003) .xls-Dateien ).

Serienartikel

• Excel-Anwendung AlgoLab.xlsm
• Sorte austauschen
• Insertion Sorts
• Nach Auswahl sortieren
• Sortierungen zusammenführen
• Nach Verteilung sortieren
• Hybridsortierung