Einführung
Manchmal können Daten, die wir in einer Anwendung speichern oder abrufen, wenig oder keine Reihenfolge haben. Möglicherweise müssen wir die Daten neu anordnen, um sie korrekt zu verarbeiten oder effizient zu verwenden. Im Laufe der Jahre haben Informatiker viele Sortieralgorithmen zum Organisieren von Daten entwickelt.
In diesem Artikel werfen wir einen Blick auf beliebte Sortieralgorithmen, verstehen, wie sie funktionieren und codieren sie in Python. Wir werden auch vergleichen, wie schnell sie Elemente in einer Liste sortieren.,
Der Einfachheit halber würden Algorithmimplementierungen Listen von Zahlen in aufsteigender Reihenfolge sortieren., Natürlich können Sie sie an Ihre Bedürfnisse anpassen
Wenn Sie etwas über einen bestimmten Algorithmus erfahren möchten, können Sie hier dazu springen:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Heap Sort
- Quick Sort
- Sorting in Python
Bubble Sort
This einfacher Sortieralgorithmus durchläuft eine Liste, vergleicht Elemente paarweise und tauscht sie aus, bis die größeren Elemente bis zum Ende der Liste „sprudeln“ und die kleineren Elemente „unten“bleiben.,
Erklärung
Zunächst vergleichen wir die ersten beiden Elemente der Liste. Wenn das erste Element größer als das zweite Element ist, tauschen wir sie aus. Wenn sie bereits in Ordnung sind, lassen wir sie so wie sie sind. Wir gehen dann zum nächsten Elementpaar über, vergleichen deren Werte und tauschen sie nach Bedarf aus. Dieser Vorgang wird bis zum letzten Elementpaar in der Liste fortgesetzt.
Wenn das Ende der Liste erreicht ist, wiederholt es diesen Vorgang für jedes Element. Dies ist jedoch sehr ineffizient. Was ist, wenn nur ein einzelner Tausch im Array vorgenommen werden muss?, Warum sollten wir immer noch iterieren, obwohl es n^2 Mal ist, obwohl es bereits sortiert ist?
Um den Algorithmus zu optimieren, müssen wir ihn natürlich stoppen, wenn er mit der Sortierung fertig ist, andernfalls wird ein bereits sortiertes Array viele Male neu bewertet.
Woher wissen wir, dass wir mit dem Sortieren fertig sind? Wenn die Artikel in Ordnung wären, müssten wir keine tauschen. Wenn wir also Werte austauschen, setzen wir ein Flag auf True, um den Sortiervorgang zu wiederholen. Wenn keine Swaps aufgetreten sind, bleibt das Flag False und der Algorithmus stoppt.,
Implementierung
Mit der Optimierung können wir die Blasensortierung in Python wie folgt implementieren:
Der Algorithmus wird in einer while – Schleife ausgeführt, die nur unterbrochen wird, wenn keine Elemente ausgetauscht werden. Wir setzen swapped am Anfang auf True, um sicherzustellen, dass der Algorithmus mindestens einmal ausgeführt wird.
Zeitkomplexität
Im schlimmsten Fall (wenn die Liste in umgekehrter Reihenfolge ist) müsste dieser Algorithmus jedes einzelne Element des Arrays austauschen., Unserswapped Flag würde bei jeder Iteration aufTrue gesetzt.
Wenn wir also n Elemente in unserer Liste haben, hätten wir n Iterationen pro Element – daher ist die Zeitkomplexität der Sortierung O(n^2).
Auswahl sortieren
Dieser Algorithmus segmentiert die Liste in zwei Teile: sortiert und unsortiert. Wir entfernen kontinuierlich das kleinste Element des unsortierten Segments der Liste und hängen es an das sortierte Segment an.,
Erklärung
In der Praxis müssen wir keine neue Liste für die sortierten Elemente erstellen, sondern den linken Teil der Liste als sortiertes Segment behandeln. Wir durchsuchen dann die gesamte Liste nach dem kleinsten Element und tauschen es mit dem ersten Element aus.
Jetzt wissen wir, dass das erste Element der Liste sortiert ist, wir erhalten das kleinste Element der verbleibenden Elemente und tauschen es mit dem zweiten Element aus. Dies wiederholt sich, bis das letzte Element der Liste das verbleibende zu untersuchende Element ist.,
Implementierung
Wir sehen, dass wir, wenn i zunimmt, weniger Elemente überprüfen müssen.
Zeitkomplexität
Wir können die Zeitkomplexität leicht ermitteln, indem wir die for – Schleifen im Auswahlsortieralgorithmus untersuchen. Für eine Liste mit n Elementen iteriert die äußere Schleife n mal.
Die innere Schleife iteriert n-1, wenn i gleich 1 ist, und dann n-2, wenn i gleich 2 ist und so weiter.
Die Anzahl der Vergleiche ist (n - 1) + (n - 2) + ... + 1, was der Auswahlsortierung eine Zeitkomplexität von O(n^2) gibt.,
Insertion Sort
Wie Selection Sort segmentiert dieser Algorithmus die Liste in sortierte und unsortierte Teile. Es iteriert über das unsortierte Segment und fügt das angezeigte Element an die richtige Position der sortierten Liste ein.
Erklärung
Wir gehen davon aus, dass das erste Element der Liste sortiert ist. Wir gehen dann zum nächsten element, nennen wir es x. Wenn x größer ist als die erste element, das wir verlassen, wie Sie ist., Wenn x kleiner ist, kopieren wir den Wert des ersten Elements an die zweite Position und setzen dann das erste Element auf x.
Wenn wir zu den anderen Elementen des unsortierten Segments gehen, verschieben wir kontinuierlich größere Elemente im sortierten Segment in die Liste, bis wir auf ein Element stoßen, das kleiner als x oder erreichen das Ende des sortierten Segments und platzieren dann x an der richtigen Position.
Wenn Sie einen ausführlichen, speziellen Artikel zur Einfügesortierung lesen möchten, haben wir Sie abgedeckt!,
Implementierung
Zeitkomplexität
Im schlimmsten Fall würde ein Array in umgekehrter Reihenfolge sortiert. Die äußere for loop in der Sortierfunktion iteriert immer n-1 mal.
Heap-Sortierung
Dieser beliebte Sortieralgorithmus segmentiert die Liste wie die Einfüge-und Auswahlsortierungen in sortierte und unsortierte Teile. Es konvertiert das unsortierte Segment der Liste in eine Heap-Datenstruktur, sodass wir das größte Element effizient bestimmen können.,
Erklärung
Wir beginnen damit, die Liste in einen maximalen Heap umzuwandeln – einen Binärbaum, bei dem das größte Element der Stammknoten ist. Wir platzieren dieses Element dann am Ende der Liste. Wir erstellen dann unseren maximalen Heap neu, der jetzt einen Wert weniger hat, und platzieren den neuen größten Wert vor dem letzten Element der Liste.
Wir iterieren diesen Prozess zum Erstellen des Heaps, bis alle Knoten entfernt sind.
Wenn Sie einen detaillierten, speziellen Artikel für die Heap-Sortierung lesen möchten, haben wir Sie abgedeckt!,
Implementierung
Wir erstellen eine Hilfsfunktion heapify um diesen Algorithmus zu implementieren:
Zeitkomplexität
Schauen wir uns zunächst die Zeitkomplexität der Funktion heapify an. Im schlimmsten Fall ist das größte Element niemals das Stammelement, dies führt zu einem rekursiven Aufruf von heapify. Während rekursive Aufrufe entmutigend teuer erscheinen mögen, denken Sie daran, dass wir mit einem Binärbaum arbeiten.
Visualisieren Sie einen Binärbaum mit 3 Elementen, er hat eine Höhe von 2., Visualisieren Sie nun einen Binärbaum mit 7 Elementen mit einer Höhe von 3. Der Baum wächst logarithmisch zu n. Dieheapify Funktion durchquert diesen Baum in O(log(n)) Zeit.
Die Funktion heap_sort iteriert n mal über das Array. Daher ist die Gesamtzeitkomplexität des Heap-Sortieralgorithmus O(nlog(n)).
Zusammenführen Sortieren
Dieser Divide and Conquer-Algorithmus teilt eine Liste in zwei Hälften und teilt die Liste weiterhin durch 2 auf, bis sie nur noch singuläre Elemente enthält.,
Benachbarte Elemente werden zu sortierten Paaren, dann werden sortierte Paare zusammengeführt und auch mit anderen Paaren sortiert. Dieser Vorgang wird fortgesetzt, bis wir eine sortierte Liste mit allen Elementen der unsortierten Eingabeliste erhalten.
Erklärung
Wir teilen die Liste rekursiv in zwei Hälften, bis wir Listen mit Größe eins haben. Wir verschmelzen dann jede Hälfte, die geteilt wurde,und sortieren sie dabei.
Die Sortierung erfolgt durch Vergleich der kleinsten Elemente jeder Hälfte. Das erste Element jeder Liste ist das erste, das verglichen wird. Wenn die erste Hälfte mit einem kleineren Wert beginnt, fügen wir diese der sortierten Liste hinzu., Wir vergleichen dann den zweitkleinsten Wert der ersten Hälfte mit dem ersten kleinsten Wert der zweiten Hälfte.
Jedes Mal, wenn wir den kleineren Wert am Anfang einer Hälfte auswählen, verschieben wir den Index, welcher Artikel um eins verglichen werden muss.
Wenn Sie einen ausführlichen, speziellen Artikel für Merge Sort lesen möchten, haben wir Sie abgedeckt!
Implementierung
Beachten Sie, dass die merge_sort() – Funktion im Gegensatz zu den vorherigen Sortieralgorithmen eine neue Liste zurückgibt, die sortiert wird, anstatt die vorhandene Liste zu sortieren.,
Daher benötigt Merge Sort Platz, um eine neue Liste mit der gleichen Größe wie die Eingabeliste zu erstellen.
Zeitkomplexität
Schauen wir uns zunächst die Funktion merge an. Es dauert zwei Listen und iteriert n mal, wobei n die Größe ihrer kombinierten Eingabe ist.
Die Funktion merge_sort teilt das angegebene Array in 2 auf und sortiert rekursiv die Unterarrays. Da die rekursive Eingabe die Hälfte dessen ist, was gegeben wurde, wie binäre Bäume, wächst die Zeit, die benötigt wird, um logarithmisch zu n zu verarbeiten.,
Daher ist die Gesamtzeitkomplexität des Zusammenführungssortieralgorithmus O(nlog (n)).
Schnellsortierung
Dieser Divide – and-Conquer-Algorithmus ist der am häufigsten verwendete Sortieralgorithmus, der in diesem Artikel behandelt wird. Bei korrekter Konfiguration ist es äußerst effizient und erfordert nicht den zusätzlichen Speicherplatz, den Merge Sort verwendet. Wir teilen die Liste um ein Pivot-Element und sortieren Werte um den Pivot.
Erklärung
Die schnelle Sortierung beginnt mit der Partitionierung der Liste – Auswahl eines Werts der Liste, der sich an seiner sortierten Stelle befindet. Dieser Wert wird als Pivot bezeichnet., Alle Elemente, die kleiner als der Drehpunkt sind, werden nach links verschoben. Alle größeren Elemente werden nach rechts verschoben.
Da wir wissen, dass sich der Pivot an seinem rechtmäßigen Platz befindet, sortieren wir die Werte rekursiv um den Pivot, bis die gesamte Liste sortiert ist.
Wenn Sie einen detaillierten, dedizierten Artikel für die schnelle Sortierung lesen möchten, haben wir Sie abgedeckt!
Implementierung
Zeitkomplexität
Im schlimmsten Fall wird immer das kleinste oder größte Element als Drehpunkt ausgewählt. Dies würde Partitionen der Größe n-1 erstellen, was zu rekursiven Aufrufen n-1 mal führt., Dies führt uns zu einer Worst-Case-Zeitkomplexität von O (n^2).
Während dies ein schrecklicher Worst Case ist, wird die schnelle Sortierung stark verwendet, da die durchschnittliche Zeitkomplexität viel schneller ist. Während die partition Funktion verschachtelte while Schleifen verwendet, führt sie Vergleiche für alle Elemente des Arrays durch, um seine Swaps durchzuführen. Als solches hat es eine Zeitkomplexität von O (n).
Bei einem guten Pivot würde die Schnellsortierfunktion das Array in Hälften unterteilen, die logarithmisch mit n. Daher ist die durchschnittliche Zeitkomplexität des Schnellsortieralgorithmus O(nlog(n)).,
Pythons integrierte Sortierfunktionen
Während es vorteilhaft ist, diese Sortieralgorithmen zu verstehen, würden Sie in den meisten Python-Projekten wahrscheinlich die Sortierfunktionen verwenden, die bereits in der Sprache bereitgestellt wurden.,
Wir können unsere Liste so ändern, dass der Inhalt mit der Methode sort() sortiert wird:
apples_eaten_a_day = apples_eaten_a_day.sort()print(apples_eaten_a_day) # Oder wir können die Funktion sorted() verwenden, um eine neue sortierte Liste zu erstellen:
apples_eaten_a_day_2 = sorted_apples = sorted(apples_eaten_a_day_2)print(sorted_apples) # Beide sortieren in aufsteigender Reihenfolge, aber Sie können leicht in absteigender Reihenfolge sortieren, indem Sie das reverse flag auf True:
Im Gegensatz zu den von uns erstellten Sortieralgorithmusfunktionen können beide Funktionen Listen von Tupeln und Klassen sortieren., Die sorted() Funktion kann jedes iterierbare Objekt sortieren und das beinhaltet – Listen, Strings, Tupel, Wörterbücher, Sets und benutzerdefinierte Iteratoren, die Sie erstellen können.
Diese Sortierfunktionen implementieren den Tim-Sortieralgorithmus, einen Algorithmus, der von Merge Sort und Insertion Sort inspiriert ist.
Geschwindigkeitsvergleiche
Um eine Vorstellung davon zu bekommen, wie schnell sie funktionieren, generieren wir eine Liste von 5000 Zahlen zwischen 0 und 1000. Wir wissen dann, wie lange es dauert, bis jeder Algorithmus abgeschlossen ist. Dies wird 10 Mal wiederholt, damit wir ein Leistungsmuster zuverlässiger feststellen können.,
Dies waren die Ergebnisse, die Zeit ist in Sekunden:
Sie würden unterschiedliche Werte erhalten, wenn Sie den Test selbst einrichten, aber die beobachteten Muster sollten gleich oder ähnlich sein. Bubble Sort ist der langsamste und schlechteste Performer aller Algorithmen. Während es als Einführung in die Sortierung und Algorithmen nützlich ist, ist es nicht für den praktischen Gebrauch geeignet.
Wir stellen auch fest, dass Quick Sort sehr schnell ist, fast doppelt so schnell wie Merge Sort und nicht so viel Platz zum Ausführen benötigt. Denken Sie daran, dass unsere Partition auf dem mittleren Element der Liste basiert, verschiedene Partitionen können unterschiedliche Ergebnisse haben.,
Da die Einfügesortierung viel weniger Vergleiche als die Auswahlsortierung durchführt, sind die Implementierungen normalerweise schneller, aber in diesen Läufen ist die Auswahlsortierung etwas schneller.
Insertion Sorts macht viel mehr Swaps als Auswahl sortieren. Wenn das Austauschen von Werten wesentlich mehr Zeit in Anspruch nimmt als das Vergleichen von Werten, wäre dieses „gegenteilige“ Ergebnis plausibel.
Achten Sie bei der Auswahl Ihres Sortieralgorithmus auf die Umgebung, da dies die Leistung beeinträchtigt.
Fazit
Sortieralgorithmen geben uns viele Möglichkeiten, unsere Daten zu bestellen., Wir sahen uns an 6 verschiedenen algorithmen – Bubble Sort, Selection Sort, Insertion Sort, Merge-Sort, Heap-Sort, Quick-Sort – und Ihre Implementierung in Python.
Die Menge an Vergleichen und Swaps, die der Algorithmus zusammen mit der Umgebung durchführt, die der Code ausführt, sind wichtige Leistungsdeterminanten. In echten Python-Anwendungen wird empfohlen, dass wir uns an die integrierten Python-Sortierfunktionen halten, da sie flexibel in Bezug auf Eingabe und Geschwindigkeit sind.