Eine Tour durch die Top 5 Sortieralgorithmen mit Python-Code


Sortieralgorithmen Komplexität‘

Sortierung ist eine Fähigkeit, die jeder Software-Ingenieur und Entwickler braucht einige Kenntnisse. Nicht nur um Codierungsinterviews zu bestehen, sondern als allgemeines Verständnis der Programmierung selbst., Die verschiedenen Sortieralgorithmen sind ein perfektes Beispiel dafür, wie Algorithmusdesign einen so starken Einfluss auf Programmkomplexität, Geschwindigkeit und Effizienz haben kann.

Lassen Sie uns einen Rundgang durch die Top 6 Sortieralgorithmen machen und sehen, wie wir sie in Python implementieren können!

Bubble sort wird normalerweise in einführenden CS-Klassen unterrichtet, da es deutlich zeigt, wie sort funktioniert, während es einfach und leicht zu verstehen ist. Bubble sortieren Schritte durch die Liste und vergleicht benachbarte Paare von Elementen. Die Elemente werden ausgetauscht, wenn sie in der falschen Reihenfolge sind., Der Durchlauf durch den unsortierten Teil der Liste wird wiederholt, bis die Liste sortiert ist. Da die Blasensortierung wiederholt den unsortierten Teil der Liste durchläuft, hat sie eine Worst-Case-Komplexität von O(n2).

Auswahlsortierung

Die Auswahlsortierung ist ebenfalls recht einfach, übertrifft jedoch häufig die Blasensortierung., Wenn Sie zwischen den beiden wählen, ist es am besten, nur Standardrecht auf Auswahl sortieren. Bei der Auswahlsortierung teilen wir unsere Eingabeliste / unser Eingabearray in zwei Teile auf: die Unterliste der bereits sortierten Elemente und die Unterliste der noch zu sortierenden Elemente, aus denen der Rest der Liste besteht. Wir finden zuerst das kleinste Element in der unsortierten Unterliste und platzieren es am Ende der sortierten Unterliste. Daher greifen wir kontinuierlich nach dem kleinsten unsortierten Element und platzieren es in sortierter Reihenfolge in der sortierten Unterliste. Dieser Vorgang wird iterativ fortgesetzt, bis die Liste vollständig sortiert ist.,

Insertion Sort

Insertion sort ist schneller und naja-wohl mehr simpel als bubble-sort und selection-sort. Komisch genug, es ist, wie viele Leute ihre Karten sortieren, wenn sie ein Kartenspiel spielen! Bei jeder Schleifeniteration entfernt insertion sort ein Element aus dem Array., Es findet dann den Speicherort, zu dem dieses Element gehört, in einem anderen sortierten Array und fügt es dort ein. Es wiederholt diesen Vorgang, bis keine Eingabeelemente mehr vorhanden sind.

Merge Sort

Merge sort ist ein perfekt elegantes Beispiel für einen Divide and Conquer Algorithmus., Es verwendet einfach die 2 Hauptschritte eines solchen Algorithmus:

(1) Teilen Sie die unsortierte Liste kontinuierlich auf, bis Sie N Unterlisten haben, wobei jede Unterliste 1 Element hat, das „unsortiert“ ist, und N die Anzahl der Elemente im ursprünglichen Array ist.

(2) Wiederholt zusammenführen, dh die Unterlisten zweimal zusammenführen, um neue sortierte Unterlisten zu erstellen, bis alle Elemente vollständig zu einem einzigen sortierten Array zusammengeführt wurden.,

Quick Sort

Quick sort ist auch ein Divide-and-Conquer-Algorithmus wie merge sort. Obwohl es etwas komplizierter ist, ist es in den meisten Standardimplementierungen deutlich schneller als die Zusammenführungssortierung und erreicht selten die Worst-Case-Komplexität von O(n2)., Es hat 3 Hauptschritte:

(1) Wir wählen zuerst ein Element aus, das wir den Pivot aus dem Array aufrufen werden.

(2) Verschieben Sie alle Elemente, die kleiner als der Drehpunkt sind, nach links vom Drehpunkt; Verschieben Sie alle Elemente, die größer als der Drehpunkt sind, nach rechts vom Drehpunkt. Dies wird als Partitionsoperation bezeichnet.

(3) Wenden Sie die obigen 2 Schritte rekursiv separat auf jedes der Unterarrays von Elementen mit kleineren und größeren Werten als dem letzten Pivot an.,

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.