Schnellster Sortieralgorithmus in C++

1. Schnellster Sortieralgorithmus in C++
2. Algorithmuskomplexitäts-Spickzettel

In diesem Artikel wird erläutert, welcher Sortieralgorithmus unter welchen Bedingungen am besten funktioniert. Zu den Bedingungen gehören der Typ der Datenstruktur, die Größe der zu sortierenden Daten, die Datenanordnung und der Bereich der Datenelemente.

Lassen Sie uns zuerst den Sortieralgorithmus erklären; Anschließend erläutern wir die Leistung verschiedener Algorithmen in den verschiedenen Datenstrukturen.

Schnellster Sortieralgorithmus in C++

Der Sortieralgorithmus ist eine Methode zum Anordnen des in einer beliebigen Datenstruktur gespeicherten Elements.

Die Eignung eines beliebigen Sortieralgorithmus hängt von der Größe der Eingabedaten, der Art der Datenstruktur, der Anordnung der Daten, der zeitlichen und räumlichen Komplexität und dem Umfang der Daten ab.

Einige Sortieralgorithmen funktionieren besser bei Array-Datenstrukturen, während andere besser bei Heaps funktionieren. Außerdem sind einige Algorithmen schnell, wenn der signifikanteste ganzzahlige Schlüssel der Datensätze viel kleiner ist als die Anzahl der Datensätze (z. B. zählendes Sortieren).

Also, welcher ist der schnellste Algorithmus? Obwohl die Antwort einfach erscheint, sehen Sie sich die Komplexitätstabelle an und wählen Sie eine mit der niedrigsten Zeitkomplexität (d. h. asymptotisches Wachstum).

In Wirklichkeit können wir jedoch nicht direkt sagen, dass Algorithmus A bei gegebenen Daten besser abschneidet als Algorithmus B oder umgekehrt, ohne die strukturellen Eigenschaften der zugrunde liegenden Daten zu sehen.

Daher werden wir versuchen, der Antwort gerecht zu werden, indem wir Sortieralgorithmen mit ihrer besonderen Eignung in verschiedenen Szenarien über einer bestimmten zugrunde liegenden Datenstruktur diskutieren.

Datenstruktur - Verkettete Liste

Die Verbindungsliste ist eine lineare Datenstruktur, die Daten im Knoten speichert. Ein Knoten ist ein grundlegender Baustein der Verbindungsliste, die Daten und einen Zeiger auf den nächsten Knoten enthält.

Der beste Sortieralgorithmus zum Sortieren einer Linkliste ist das Merge-Sortieren. Zusammenführungssortierung funktioniert bei verknüpften Listen besser als bei Arrays, da kein zusätzliches Array erforderlich ist, um die Ausgabe der Zusammenführungsoperation zu speichern.

Im Gegensatz zu Arrays müssen verknüpfte Listenknoten im Speicher nicht zusammenhängend sein. Stattdessen können die Knoten an verschiedenen Speicherorten verstreut sein.

Außerdem können wir im Gegensatz zu einem Array einen Wert in der Mitte einer verknüpften Liste in O(1) zusätzlichem Raum und O(1) Zeit platzieren.

Als Ergebnis wird kein zusätzlicher asymptotisch wachsender Platz benötigt, um die Zusammenführungsoperation der Zusammenführungssortierung beim Sortieren der Verknüpfungsliste zu implementieren. Daher sortiert Mergesort die Linkliste in (nlog n).

Die Implementierung der Zusammenführungssortierung finden Sie hier.

Datenstruktur - Array

Das Array ist die lineare Datenstruktur, die Daten an einer fortlaufenden Speicherstelle speichert. Der Datentyp muss in einem Array gleich sein.

Hier ist eine Liste der verschiedenen Sortieralgorithmen und ihrer Eignung.

• Einfügesortierung könnte gewählt werden, wenn das Array fast sortiert ist, da es selten Elemente verschiebt, wenn ein neues Element in den sortierten Bereich des Arrays hinzugefügt wird.

  Die zeitliche Komplexität einer Einfügungssortierung in einem sortierten Array ist O(n), aber die zeitliche Komplexität der schnellen Sortierung in demselben Array ist O(n^2). Weitere Informationen finden Sie hier.

• Da Quick Sort eine In-Place-Sortierung durchführt, ist es für Arrays geeignet. Außerdem benötigt der schnelle Sortieralgorithmus keinen zusätzlichen Platz während des Sortiervorgangs.

• Im Fall von Mergesort muss der zusätzliche Speicherplatz erworben und freigegeben werden. Daher wird die Ausführungszeit des Mischsortieralgorithmus erhöht.

  Zusammenführen und schnelles Sortieren haben im Durchschnitt eine O(nlogn)-Zeitkomplexität, aber das Zusammenführen und Sortieren benötigt zusätzlichen O(n)-Platz. Dabei ist das n die Grösse des zu sortierenden Arrays. Mehr dazu finden Sie hier.

• Wenn wir die in einem Array gespeicherten Daten (z. B. Ganzzahlen, Wörter und Zeichenfolgen mit Zeichen fester Länge) in lexikografischer Reihenfolge sortieren möchten, verwenden wir die Radix-Sortierung. Radix-Sortierung funktioniert bei Verwendung paralleler Maschinen.

• Zählsortierung wird verwendet, wenn der größte ganzzahlige Schlüssel der Datensätze viel kleiner als die Anzahl der Datensätze ist.

• Die Bucket-Sortierung ist am effizientesten, wenn die in einem Array gespeicherten Daten innerhalb eines Bereichs gleichmäßig verteilt sind.

Datenstruktur - Baum

Der Baum ist eine nichtlineare Datenstruktur, die Daten in den Knoten speichert. Der oberste Knoten wird als root-Knoten bezeichnet. Der Wurzel-Knoten ist weiter mit den Kind-Knoten verbunden.

Es gibt viele Arten von Bäumen, aber hier diskutieren wir nur den binären Suchbaum (BST).

Die Baumsortierung gilt als der beste Sortieralgorithmus für BST. Außerdem gibt uns die In-Order-Traversierung von BST die Elemente in sortierter Reihenfolge. In ähnlicher Weise eignet sich die Heap-Sortierung am besten zum Sortieren der in einem Heap gespeicherten Elemente.

Denken Sie daran, dass wir auch alle Sortieralgorithmen für andere Arten von Datenstrukturen wie Hash-Tabellen, Rot-Schwarz-Bäume und vieles mehr analysieren können.

Der folgende Abschnitt enthält einen Spickzettel, der die Komplexität und Stabilität verschiedener Sortieralgorithmen darstellt.

Algorithmuskomplexitäts-Spickzettel

Bevor wir uns die Tabelle ansehen, lassen Sie uns allgemeine Terminologien im Zusammenhang mit Sortieralgorithmen diskutieren.

Stabile Sortierung

Ein Algorithmus ist stabil, wenn er bei einem Gleichstand zwischen den Schlüsseln die ursprüngliche Reihenfolge der Schlüssel beibehält. Angenommen, die Sequenz S hat die folgenden Paare:

S = <(1,"Alex"), (3,"Bill"),(2,"Ananth"), (1, "Jack")>

Nehmen wir nun an, wir möchten die obige Sequenz nach ganzzahligen Schlüsseln sortieren. Dann sortiert ein stabiler Sortieralgorithmus die obige Sequenz wie folgt:

Stably Sorted S = <(1,"Alex"),(1, "Jack"),(2,"Ananth"),(3,"Bill")>

Sehen Sie, die stabile Sortierung hat die ursprüngliche Reihenfolge der Paare (1, Alex) und (1, Jack) beibehalten. Eine instabile Sortierung garantiert dies jedoch nicht.

In-Place-Sortierung

Eine Sortierung ist vorhanden, wenn sie eine konstante Menge an Hilfsspeicher benötigt. Das bedeutet, dass der zusätzliche Speicherbedarf nicht mit der Problemgröße zunimmt.

Zum Beispiel sind alle Sortierungen im folgenden Spickzettel mit der Raumkomplexität O(1) vorhanden.

Nachdem wir uns ausreichend mit den grundlegenden Sortierterminologien vertraut gemacht haben, schauen wir uns die Komplexitätstabelle für die Sortieralgorithmen an. Diese Tabelle kann uns bei der Entscheidung helfen, den am besten geeigneten Sortieralgorithmus in einem bestimmten Problemkontext auszuwählen.