Algorithmen: Auswahlsortierung in JavaScript

So erstellen Sie eine Schleifeninvariante für die Auswahlsortierung und implementieren den Algorithmus mithilfe der testgesteuerten Entwicklung

Die Übung

Vor kurzem habe ich Cormens Buch Einführung in Algorithmen aufgefrischt, um die Befragung von Ingenieurkandidaten bei der Arbeit zu verbessern. In Kapitel 2, in dem es um das Entwerfen und Analysieren von Algorithmen geht, wird in diesem Buch die folgende Übung vorgestellt:

Betrachten Sie das Sortieren von n in Array A gespeicherten Zahlen, indem Sie zuerst das kleinste Element von A finden und es mit dem Element in A [1] austauschen. Finden Sie dann das zweitkleinste Element von A und tauschen Sie es mit A aus [2]. Fahren Sie auf diese Weise für die ersten n-1 Elemente von A fort. Schreiben Sie einen Pseudocode für diesen Algorithmus, der als Auswahlsortierung bekannt ist. Welche Schleifeninvariante behält dieser Algorithmus bei? Warum muss es nur für die ersten n-1 Elemente und nicht für alle n Elemente ausgeführt werden? Geben Sie die Best- und Worst-Case-Laufzeiten der Auswahlsortierung in Ɵ-Notation an.

Ich denke, dies ist eine großartige Frage, da sie den gesamten Denkprozess beim Entwerfen eines Algorithmus abdeckt. Wir kennen die Grundidee, wie es funktionieren soll (Finden und Austauschen des kleinsten Elements für jeden Index), aber woher wissen wir, dass unsere Implementierung korrekt ist? Welche Bedingungen können wir festlegen, um sicherzustellen, dass jede Iteration die richtigen Aktionen ausführt? Und wie effizient ist der Algorithmus? Was ist die Laufzeit?

Dies sind alles Fragen, die wir für die Auswahlsortierung behandeln werden. Ich habe gerade einen sehr ähnlichen Artikel über die Sortierung von Einfügungen in JavaScript veröffentlicht, den Sie hier finden:

In diesem Beitrag habe ich zunächst die Implementierung des Algorithmus vorgestellt und dann die Korrektheits- und Laufzeitanalyse behandelt. Dieses Mal werde ich jedoch zunächst die Schleifeninvariante festlegen und diese dann verwenden, um meine Codeimplementierung in JavaScript zu informieren. Auf diese Weise führen wir im Grunde genommen Test-Driven Development (TDD) durch, um sie zu implementieren der Algorithmus. Sobald wir dies getan haben, werden wir mit der Laufzeitanalyse unserer Implementierung abschließen.

Die Invariante der Auswahlsortierschleife

Wie in der Übung beschrieben, iteriert die Auswahlsortierung über die Eingabe, findet das kleinste verbleibende Element und tauscht es in den aktuellen Index aus. Ziemlich einfach! – aber hier ist ein nettes GIF, das ich gemacht habe, um dir zu helfen, es zu visualisieren :).

Wie wäre die Schleifeninvariante für diesen Algorithmus? Zur Erinnerung: Die Schleifeninvariante ist eine einzelne Bedingung oder ein Satz von Bedingungen, die der Algorithmus zu Beginn, am Ende und während jeder Iteration seiner Ausführung beibehält. Nehmen Sie sich ein oder zwei Minuten Zeit, um darüber nachzudenken, bevor Sie weiterlesen! Welche Eigenschaften können wir überprüfen, um sicherzustellen, dass unser Algorithmus korrekt ausgeführt wird?

Lassen Sie uns jetzt gemeinsam darauf kommen. Basierend auf dem, was wir für die Funktionsweise des Algorithmus beschrieben haben, wissen wir, dass das kleinste verbleibende Element immer zuerst gefunden und sortiert wird. Nach einer Iteration befindet sich das kleinste Element am Index 0, nach zwei Iterationen werden die beiden kleinsten Elemente sortiert und so weiter und so fort. Diese Eigenschaft gibt uns einen guten Zustand zu überprüfen.

Die für die Auswahlsortierung invariante Schleife besteht darin, dass die Elemente des neu sortierten Arrays bis zum aktuellen Index A [0..i] enthält die i kleinsten Elemente unserer ursprünglichen Eingabe, A [ 0..n-1] . Sie werden auch in sortierter Reihenfolge angezeigt.

Wenn diese Bedingung vor, während und am Ende unserer Algorithmusausführung gilt, können wir sicher sein, dass sie korrekt ausgeführt wird.

Hier ist der Code für die Schleifeninvariante, die wir gerade erstellt haben. Es erfordert das Sortier-in-Progress-Array, das ursprüngliche Eingabearray und den aktuellen Index.

Wir werden diese Funktion verwenden, um unsere Auswahlsortierfunktion zu implementieren.

HINWEIS - Ich betrüge ein wenig und verwende die integrierte Sortierfunktion im JavaScript-Array, um die kleinsten i -Werte in der ursprünglichen Eingabe zu finden. Es gibt andere Möglichkeiten, dies zu tun, aber wir werden diese Funktion einfach im Wesentlichen als Komponententest verwenden.

Implementieren der Auswahlsortierung

Nachdem wir nun unsere schleifeninvariante Funktion haben, können wir einen TDD-Ansatz (Test Driven Development) zur Implementierung des Algorithmus verwenden. Verwenden Sie dieselbe Eingabe wie im obigen Diagramm.

Dann können wir eine Skelettfunktion für die Auswahlsortierung erstellen und unsere schleifeninvariante Testfunktion aufrufen.

Wir müssen nur zu nums.length - 1 iterieren, da wir, wenn Sie darüber nachdenken, das Element an jedem Index ständig mit dem kleinsten verbleibenden Element rechts im Array austauschen. Wenn wir den endgültigen Index erreichen, ist er garantiert der größte, sodass wir ihn nicht verarbeiten müssen.

Wenn wir nun console.log (selectionSort (input)) ausführen, erhalten wir die folgende Ausgabe in unserer Konsole:

Dies ist eigentlich eine gute Sache, da dies der Beginn unseres TDD-Ansatzes ist! Wir möchten den Algorithmus implementieren, bis alle Fehler verschwunden sind und das endgültige Rückgabearray in sortierter Reihenfolge vorliegt.

Das Innere der Schleife ist eigentlich ziemlich einfach. Wir greifen das Element am aktuellen Index i zu und überprüfen dann den Rest des Arrays auf Elemente, die kleiner als dieses sind. Wenn Sie das kleinste Element gefunden haben und es sich noch nicht im aktuellen Index befindet, tauschen Sie es gegen das kleinste aus.

Wenn Sie diesen Code mit den Schleifeninvariantenprüfungen in den obigen Skelettcode einfügen, werden Sie feststellen, dass alle unsere Fehler verschwunden sind und nur das Endergebnis ausgegeben wird!

Unser endgültiger Algorithmus lautet:

Laufzeitanalyse der Auswahlsortierung

Wir werden diesen Beitrag mit einer Laufzeitanalyse des Auswahlsortieralgorithmus abschließen.

Wie wir im vorherigen Abschnitt erfahren haben, muss der Auswahlsortieralgorithmus nur bis zum Element n-1 ausgeführt werden. In diesem Sinne kann die äußere Schleife als Summation von i = 1 zu n-1 dargestellt werden. Für unsere innere Schleife müssen wir nur den Teil des Arrays durchlaufen, der noch nicht sortiert wurde. Mit anderen Worten, wenn wir i -Elemente sortiert haben, müssen wir nur n-i -Iterationen der inneren Schleife durchführen. Das gibt uns unsere Summationsformel:

Zufälligerweise ist dies genau das gleiche Ergebnis, das wir für eine Worst-Case-Einfügungssortierung erhalten haben, und es ist Ɵ (n²). Ein großer Unterschied zwischen Auswahl- und Einfügesortierung besteht jedoch darin, dass die Auswahlsortierung sowohl für den besten als auch für den schlechtesten Fall dieselbe Laufzeit hat. Es gibt keine Bedingungen, die möglicherweise die innere Schleife kurzschließen könnten. Es muss immer das gesamte Array durchlaufen, um zu überprüfen, ob keine kleineren Elemente mehr vorhanden sind. Dies bedeutet, dass die Einfügungssortierung im Durchschnitt immer ein leistungsfähigerer Algorithmus ist.

Obwohl dies bedeutet, dass die Auswahlsortierung unpraktisch ist, da es leistungsfähigere Algorithmen gibt, die denselben Job ausführen, fand ich diese Übung dennoch lehrreich und hilfreich, wenn ich mit Kandidaten und Mitarbeitern verschiedene algorithmische Ansätze diskutierte.