Technologische Neuigkeiten, Bewertungen und Tipps!

Spielen mit Code: Einfügungssortierung in Swift

Hinweis: Der folgende Artikel hilft Ihnen weiter: Spielen mit Code: Einfügungssortierung in Swift

Zurück zum Blog

Lass uns mit Code spielen! In diesem Tutorial besprechen wir, wie die Einfügungssortierung funktioniert. Es ist einer der einfachsten Sortieralgorithmen, die wir haben, was ihn zum perfekten Kandidaten für etwas gemächliches Swift-Codieren macht. Gibt es einen besseren Weg, Ihre Swift-Programmierkenntnisse zu verbessern, als an Sortieralgorithmen herumzubasteln?

Unter Sortieren versteht man das systematische Anordnen von Gegenständen nach einer vorgegebenen Regel oder Reihenfolge. Sie können Zahlen vom größten zum kleinsten, Personennamen von A bis Z und Seilstücke nach Länge sortieren.

Beim Erstellen von Apps müssen Sie möglicherweise benutzerbezogene Daten sortieren. Zum Beispiel die Namen in einem Adressbuch. Sie sortieren die Namensliste von A bis Z und präsentieren sie dem Benutzer.

Zu anderen Zeiten erfolgt die Sortierung hinter den Kulissen. Viele Suchalgorithmen können beispielsweise eine Liste effizienter durchsuchen, wenn sie bereits sortiert ist. Sie können sich vorstellen, dass Google über einen alphabetisch sortierten Index von Suchbegriffen verfügt, sodass schnell gefunden werden kann, welche Website zum Suchbegriff „Sportschuhe“ passt.

Ein Algorithmus lässt sich am besten als „eine Abfolge von Schritten, die Eingaben entgegennehmen und Ausgaben erzeugen“ definieren. Daher verarbeitet ein Sortieralgorithmus eine Sammlung – ein Array – und gibt ein sortiertes Array zurück. In einigen Fällen können Sie zusätzliche Parameter bereitstellen, beispielsweise eine Vergleichsfunktion.

Ein wichtiges Merkmal eines Sortieralgorithmus ist seine zeitliche Komplexität. Kurz gesagt, die Zeitkomplexität drückt die Zeit aus, die ein Algorithmus im Verhältnis zur Größe der Eingabe benötigt, um fertig zu werden. Die Big-O-Notation wird verwendet, um die zeitliche (und räumliche) Komplexität zu beschreiben. Ein effizienter Sortieralgorithmus wie Quicksort hat im ungünstigsten Fall eine Zeitkomplexität von O(n log n).

Es ist erwähnenswert, dass Swift Introsort als Sortieralgorithmus der Wahl verwendet. Es handelt sich um einen Hybridalgorithmus, der Quicksort und Heapsort adaptiv kombiniert, um einen generischen Algorithmus bereitzustellen, der im Durchschnitt eine gute Leistung erbringt.

Der Algorithmus, mit dem wir heute arbeiten – Einfügesortierung – hat eine Komplexität von O(n2). Wenn sich die Größe des Eingabearrays verdoppelt, vervierfacht sich die Zeit, die zum Ausführen des Einfügungssortierungsalgorithmus benötigt wird! Sie können sich vorstellen, dass dies bei großen Datensätzen ein Problem darstellt, aber für eine Übung wie diese ist es völlig in Ordnung.

Beginnen wir mit der Einfügungssortierung!

Es ist am einfachsten, die Einfügungssortierung mit dem Sortieren einer Hand (oder eines Stapels) von Spielkarten zu vergleichen.

Stellen Sie sich vor, Sie haben eine Hand mit 5 Spielkarten. Um Ihre Karten zu sortieren, nehmen Sie eine Karte heraus und bestimmen ihren sortierten Platz unter den übrigen Karten. Sie tun dies für jede Karte, um Ihre gesamte Hand zu sortieren.

Daher hat die Einfügungssortierung ihren Namen, denn Sie nehmen Gegenstände heraus und legen sie wieder an ihren sortierten Platz. Für jedes Element im Array bestimmen wir seine sortierte Stelle und fügen das Element dort ein.

Lassen Sie uns den Einfügungssortierungsalgorithmus besprechen. Wir werden dieses Array von Ganzzahlen sortieren:

[70, 36, 40, 95, 22, 55, 26]

Wir durchlaufen jedes Element im Array von links nach rechts, mit Ausnahme des ersten Elements. Die bereits sortierten Elemente landen links im Array.

So funktioniert das:

  • Wir durchlaufen jedes Element im Array von links nach rechts. Den ersten Eintrag können wir überspringen, da es sich um eine bereits sortierte Unterliste handelt.
  • Jeder Artikel wird mit der Unterliste der Artikel verglichen, die wir bereits sortiert haben, von rechts nach links, beginnend mit dem aktuellen Artikel.
  • Wenn der Algorithmus auf eine Zahl stößt, die größer als das aktuelle Element ist, wird diese Zahl um eine Position nach rechts verschoben.
  • Wenn eine Zahl gefunden wird, die kleiner als die des aktuellen Elements ist, oder wir das Ende der Unterliste erreicht haben, wird das aktuelle Element eingefügt.

Schauen wir uns ein visuelles Beispiel an:

In jedem Schritt wird von oben nach unten das orangefarbene Element mit den blauen Elementen verglichen und an der richtigen Stelle eingefügt. Also… was ist der richtige Ort?

Hier ist ein genauerer Blick auf Schritt 5. Die Zahl 55 muss irgendwo in die sortierte Unterliste eingefügt werden. Wie?

Folgendes passiert:

  1. Zuerst nehmen wir 55 heraus. Dadurch wird Platz im Array freigegeben.
  2. Dann vergleichen wir 55 mit 95, dem Item davor. 95 ist größer als 55, also verschieben wir 95 um eine Position nach rechts – in den freien Raum.
  3. Dann vergleichen wir 55 mit 70. 70 ist größer als 55, also verschieben wir 70 um eine Position nach rechts. (Gleicher Schritt wie zuvor.)
  4. Dann vergleichen wir 55 mit 40. 40 ist kleiner als 55, also fügen wir jetzt 55 in die freie Stelle ein.
  5. Erledigt! Die richtige Stelle für 55 liegt zwischen 40 und 70.

Derselbe Vorgang wird für jedes Element im Array wiederholt. Und daher erhält die Einfügungssortierung ihre O(n2)-Zeitkomplexität. Im schlimmsten Fall muss jeder Artikel mit jedem anderen Artikel verglichen werden. Anders gesagt, zwei verschachtelte Schleifen – ein verräterisches Zeichen für O(n2).

Warum können wir den ersten Punkt überspringen? Auch wenn sich Nummer 70 nicht an der endgültigen Sortierstelle befindet, wird sie aufgrund von Vergleichen mit den anderen Nummern nach rechts verschoben. Man könnte also sagen, dass eine Unterliste eines Artikels bereits sortiert ist!

Es ist an der Zeit, diesen Algorithmus tatsächlich zu programmieren. Lasst uns anfangen!

Basierend auf dem von uns entdeckten Mechanismus können wir den Einfügungssortierungsalgorithmus Schritt für Schritt codieren. Die meisten Teile sind bereits vorhanden!

Beginnen wir mit den unsortierten Zahlen. So was:

var-Zahlen = [70, 36, 40, 95, 22, 55, 26]

Wir benötigen nun etwas Code, um diese Zahlen zu durchlaufen, beginnend beim zweiten Element im Array bis zum Ende des Arrays. Hier ist wie:

für Index in 1..

  • index, das ist die Array-Indexnummer, die wir gerade iterieren
  • value, das ist der Array-Wert, den wir gerade prüfen
  • Position, das ist der Index, an dem wir den Wert einfügen werden (nachdem wir diese sortierte Position bestimmt haben)
  • Als Nächstes programmieren wir die innere Schleife, die die sortierte Unterliste durchläuft. Hier ist es:

    während Position > 0 && Zahlen[position – 1] > Wert {
    Zahlen[position] = Zahlen[position – 1]
    Position -= 1
    }

    Dies ist eine While-Schleife. Die Schleife wird so lange fortgesetzt, wie der Ausdruck wahr ist. Es ist perfekt, wenn Sie nicht wissen, wie oft eine Schleife ausgeführt werden muss (im Gegensatz zu einer for-Schleife).

    Wie funktioniert diese While-Schleife?

    • Denken Sie daran, dass wir beim Durchlaufen der Zahlen die Unterliste der sortierten Zahlen davor überprüfen werden.
    • Dazu beginnen wir beim Index und zählen rückwärts, bis wir 0 erreichen. Das ist der erste Teil der Schleife. Während die Position über Null liegt, subtrahieren Sie 1 von der Position mit Position -= 1.
    • Aber das ist noch nicht alles! Wir möchten nur dann rückwärts gehen, wenn die Zahl an der von uns untersuchten Position größer als der aktuelle Wert ist.
    • Das ist der zweite Teil der Schleife. Wenn die überprüfte Zahl größer ist als die Zahl an der aktuellen Position, verschieben Sie diese Zahl mit Zahlen um eine Position nach rechts[position] = Zahlen[position – 1].

    Sobald schließlich die Sortierposition für das aktuelle Element bestimmt ist, können wir den Wert einfach seiner neuen Position zuweisen. So was:

    Zahlen[position] = Wert

    Die Elemente, die größer als der Wert sind, wurden nach rechts verschoben. Und die while-Schleife stoppt, wenn sie auf einen Wert trifft, der kleiner als der aktuelle Wert ist. Daher können wir nun den aktuellen Wert in den freien Speicherplatz einfügen.

    Dies ist der schwierigste Schritt in diesem Algorithmus. Es lohnt sich, noch einmal vorbeizuschauen!

    Schauen wir es uns mal aus einer anderen Perspektive an. Sie wissen, dass die Einfügungssortierung auf drei Prinzipien beruht:

    • Bestimmen Sie die sortierte Position für jedes Array-Element, indem Sie das Array durchlaufen
    • Durch Verschieben von Elementen, die größer als das aktuelle Element sind, nach rechts
    • Bis ein Artikel kleiner als der aktuelle Artikel ist, fügen Sie ihn einfach ein

    Die while-Schleife macht zwei Dinge. Es verfolgt die Position und verschiebt Array-Elemente nach rechts. Dies geschieht nur, wenn die Position größer als Null ist (eine „Rücklaufsperre“) und wenn der überprüfte Wert größer als der aktuelle Wert ist.

    Technisch gesehen wird das Array in zwei Richtungen iteriert. Zuerst von links nach rechts für jedes Element. Und dann läuft die verschachtelte Schleife vom aktuellen Element aus rückwärts über die Elemente, die bereits sortiert wurden.

    Stellen Sie sich vor, Sie würden selbst physisch über diese Reihe laufen, ein bisschen wie Himmel und Hölle, und in jedes der Quadrate treten. Bei jedem Schritt nehmen Sie die Zahl unter Ihre Füße.

    Sie schauen hinter sich, um diese Zahl mit allen Zahlen zu vergleichen, die Sie zuvor sortiert haben. Sie können die Zahl nicht einfach einfügen. Um Platz zu schaffen, verschieben Sie die vorherigen Zahlen in Ihre Richtung, bis Sie genau an der richtigen Stelle etwas Platz geschaffen haben.

    Hier ist der Algorithmus, den wir bisher codiert haben. Versuche es! Verstehen Sie, wie es funktioniert?

    var-Zahlen = [70, 36, 40, 95, 22, 55, 26]

    für Index in 1.. 0 && Zahlen[position – 1] > Wert {
    Zahlen[position] = Zahlen[position – 1]
    Position -= 1
    }

    Zahlen[position] = Wert
    }

    drucken(Zahlen)

    Hier ist eine kurze Frage: Können Sie ein Zeichen ändern, damit der Sortieralgorithmus stattdessen von der größten zur kleinsten Zahl sortiert?

    Und hier ist derselbe Algorithmus, mit ausführlichen print()-Zeilen, die Sie durch die einzelnen Schritte führen. Versuche es!

    var-Zahlen = [70, 36, 40, 95, 22, 55, 26]

    print(„Wir werden diese Zahlen sortieren: \(Zahlen)“)

    für Index in 1.. 0 && Zahlen[position – 1] > Wert
    {
    print(“– \(Zahlen[position-1]) > \(Wert), also Verschiebung von \(Zahlen[position-1]) Nach rechts”)

    Zahlen[position] = Zahlen[position – 1]
    Position -= 1

    print(“-> \(Zahlen)”)
    }

    print(“– Gefundene sortierte Position von \(Wert) ist \(Position), also Einfügen“)

    Zahlen[position] = Wert

    print(“-> \(Zahlen)”)
    drucken(“”)
    }

    drucken(Zahlen)

    Die große Frage ist natürlich: Können wir diesen Algorithmus in eine Funktion umwandeln, die mit jedem Datentyp funktioniert?

    Ja! Solange die Eingabedaten für den Algorithmus dem Comparable-Protokoll entsprechen, können Sie alles sortieren, was Sie möchten. Und zur Sicherheit fügen wir sogar einen Vergleichsabschluss hinzu.

    Auf geht’s:

    func insertSort(_ input: [T]im Vergleich: (T, T) -> Bool) -> [T]
    {
    var items = Eingabe

    für Index in 1.. 0 && Vergleich(Elemente[position – 1]Wert) {
    Artikel[position] = Artikel[position – 1]
    Position -= 1
    }

    Artikel[position] = Wert
    }

    Artikel zurücksenden
    }

    var sorted = insertSort([70, 36, 40, 95, 22, 55, 26]von: >)
    drucken (sortiert)

    Var-Namen = insertSort([“Marvin”, “Arthur”, “Zaphod”, “Trillian”, “Eddie”], by: { $0 < $1 }) print(names) Was ist hier los? Der Einfügungssortierungsalgorithmus hat sich nicht geändert, aber ein paar andere Dinge haben sich geändert:

    • Die Funktion insertSort(_:by:) verwendet den generischen Platzhalter T. Und der Typ T muss Comparable entsprechen, z. B. Int oder String.
    • Der Typ des Eingabeparameters und der Rückgabetyp der Funktion sind beides [T]. Was auch immer Sie eingeben, es wird auch herauskommen. Natürlich handelt es sich bei beiden um Arrays.
    • Der Vergleichsparameter nimmt einen Abschluss vom Typ (T, T) -> Bool an. Das bedeutet, dass der Abschluss zwei Eingänge T hat und einen booleschen Wert zurückgibt.

    Innerhalb des Algorithmus nennen wir den Vergleichsabschluss und stellen ihm die beiden Werte bereit, die verglichen werden müssen. Erinnern Sie sich, wie wir diesen Vergleich zur Steuerung der Sortierung im Algorithmus verwendet haben? Dank der Schließung können Sie jetzt Ihre eigene Vergleichsfunktion bereitstellen!

    Das sehen Sie am Ende für die Arrays „sorted“ und „names“. Für sortiert stellen wir lediglich den logischen Operator „Größer als >“ bereit. Dieser Operator nimmt zwei Eingaben entgegen, die linke und die rechte Seite, und gibt einen booleschen Wert zurück. Die Implementierung ist im Wesentlichen genau die gleiche wie zuvor.

    Und für Namen stellen wir den Abschluss { $0 < $1 } bereit. Es verwendet die Abkürzung $n, um auf die Eingabeparameter des Abschlusses zu verweisen, und vergleicht sie mit dem logischen Operator „Kleiner als <“. Dabei werden wie zuvor die beiden Array-Elemente miteinander verglichen, um deren Sortierreihenfolge zu bestimmen.

    Eindrucksvoll! Wenn man sich einmal damit beschäftigt, sind diese Algorithmen gar nicht so schwer zu verstehen. Und es ist ziemlich cool, von einem Algorithmus auf Papier zu funktionierendem Code zu gelangen und etwas zu schreiben, das Sie in Ihrer täglichen Programmierung verwenden können.

    Table of Contents