Sortieralgorithmen erklärt

Programmierung

Sortieralgorithmen sind eine Reihe von Anweisungen, die ein Array oder eine Liste als Eingabe verwenden und die Elemente in einer bestimmten Reihenfolge anordnen.

Sortierungen sind am häufigsten in numerischer oder alphabetischer (lexikografischer) Reihenfolge und können in aufsteigender (AZ, 0-9) oder absteigender (ZA, 9-0) Reihenfolge erfolgen.

Warum Sortieralgorithmen wichtig sind

Da das Sortieren häufig die Komplexität eines Problems verringern kann, ist es ein wichtiger Algorithmus in der Informatik. Diese Algorithmen haben direkte Anwendungen in Suchalgorithmen, Datenbankalgorithmen, Divide- und Conquer-Methoden, Datenstrukturalgorithmen und vielem mehr.

Einige gängige Sortieralgorithmen

Einige der gebräuchlichsten Sortieralgorithmen sind:

  • Auswahl Sortieren
  • Blasensortierung
  • Sortieren durch Einfügen
  • Zusammenführen, sortieren
  • Schnelle Sorte
  • Heap Sort
  • Sortierung zählen
  • Radix Sort
  • Eimersortierung

Klassifizierung des Sortieralgorithmus

Sortieralgorithmen können anhand der folgenden Parameter kategorisiert werden:

  1. Basierend auf der Anzahl der Swaps oder der Inversion Dies ist die Häufigkeit, mit der der Algorithmus Elemente austauscht, um die Eingabe zu sortieren. Selection Sorterfordert die Mindestanzahl von Swaps.
  2. Basierend auf der Anzahl der Vergleiche Dies ist die Häufigkeit, mit der der Algorithmus Elemente vergleicht, um die Eingabe zu sortieren. Unter Verwendung der Big-O-Notation erfordern die oben aufgeführten Beispiele für Sortieralgorithmen mindestens O(nlogn)Vergleiche im besten Fall und O(n^2)Vergleiche im schlechtesten Fall für die meisten Ausgaben.
  3. Basierend auf Rekursion oder Nicht-Rekursion Einige Sortieralgorithmen, z. B. Quick Sortrekursive Techniken, um die Eingabe zu sortieren. Andere Sortieralgorithmen wie Selection Sortoder Insertion Sortverwenden nicht rekursive Techniken. Schließlich verwenden einige Sortieralgorithmen, wie z. B. Merge Sortsowohl rekursive als auch nicht rekursive Techniken, um die Eingabe zu sortieren.
  4. Basierend auf Stabilität werden Sortieralgorithmen genannt, stablewenn der Algorithmus die relative Reihenfolge von Elementen mit gleichen Schlüsseln beibehält. Mit anderen Worten, zwei äquivalente Elemente bleiben in der sortierten Ausgabe in derselben Reihenfolge wie in der Eingabe.
  5. Insertion sort,, Merge Sortund Bubble Sortsind stabil
  6. Heap Sortund Quick Sortsind nicht stabil
  7. Basierend auf zusätzlichen Platzanforderungen Sortieralgorithmen werden verwendet, in placewenn sie einen konstanten O(1)zusätzlichen Platz zum Sortieren benötigen .
  8. Insertion sortund Quick-sortsind in placesortiert, wenn wir die Elemente um den Pivot verschieben und kein separates Array verwenden, was bei der Zusammenführungssortierung NICHT der Fall ist, bei der die Größe der Eingabe im Voraus zugewiesen werden muss, um die Ausgabe während der Sortierung zu speichern.
  9. Merge Sortist ein Beispiel für das out placeSortieren, da es zusätzlichen Speicherplatz für seine Operationen benötigt.

Bestmögliche Zeitkomplexität für jede vergleichsbasierte Sortierung

Jeder vergleichsbasierte Sortieralgorithmus muss mindestens nLog2n-Vergleiche durchführen, um das Eingabearray zu sortieren, und Heapsort- und Merge-Sortierung sind asymptotisch optimale Vergleichssortierungen. Dies kann leicht durch Zeichnen des Entscheidungsbaumdiagramms bewiesen werden.