Sortierung ist eine der grundlegendsten und nützlichsten Funktionen für Daten. Ziel ist es, Daten auf eine bestimmte Art und Weise anzuordnen, die je nach Anforderung zunehmen oder abnehmen kann. In C ++ STL gibt es eine integrierte Funktion mit dem Namen 'sort ()', mit der wir den Sortieralgorithmus einfach ausführen können. In diesem Artikel werden wir die Sortierfunktion in C ++ untersuchen.
Folgende Hinweise werden in diesem Artikel behandelt:
- Sort () Funktion
- Beispiel - Daten in aufsteigender Reihenfolge sortieren
- Beispiel - Zum Sortieren von Daten in absteigender Reihenfolge
- Partial_sort
Fahren Sie mit diesem Artikel über die Sortierfunktion in C ++ fort
Sortieren (( ) Funktion
Es ist eine integrierte Funktion der Algorithmus-Header-Datei, mit der die Container wie ein Array sortiert werden, Vektoren in einer bestimmten Reihenfolge. Intern ist diese Funktion als Quick-Sort implementiert
Quicksort ist ein Divide and Conquer-Algorithmus. Quicksort unterteilt zunächst eine große Liste von Elementen in zwei kleinere Unterlisten: die unteren und die höheren Elemente. Quicksort sortiert dann die Unterlisten rekursiv.
Die Schritte sind wie folgt:
1. Wählen Sie aus der Liste ein zufälliges Element (normalerweise das letzte Element) aus, das als Pivot bezeichnet wird.
2. Ordnen Sie die Liste so neu an, dass alle Elemente mit Werten, die kleiner als der Pivot sind, vor dem Pivot stehen, während alle Elemente mit Werten, die größer als der Pivot sind, danach kommen und gleiche Werte in beide Richtungen gehen können. Dies wird als Partitionsoperation bezeichnet.
3. Sortieren Sie rekursiv die Unterliste kleinerer Elemente und die Unterliste größerer Elemente, wählen Sie erneut einen Drehpunkt in der Unterliste aus und teilen Sie sie.
Der Grundfall der Rekursion sind Listen der Größe Null oder Eins, die niemals sortiert werden müssen. Durch Sortieren sortieren wir unsere Liste.
Klassenpfad für Java festlegen
Quicksort ist in der Praxis schneller als andere O (n log n) -Algorithmen wie Insertion Sort oder Bubble Sort. Quicksort kann mit einem direkten Partitionierungsalgorithmus implementiert werden, was bedeutet, dass die gesamte Sortierung mit nur O (log n) zusätzlichem Speicherplatz durchgeführt werden kann. Quicksort ist keine stabile Sorte.
Seine Komplexität ist wie folgt:
Bester Fall - O (n log n)
Schlimmster Fall - O (n ^ 2)
Durchschnittlicher Fall - O (n log n)
Syntax:
sortieren (zuerst, zuletzt)
Hier,
first - ist der Index (Zeiger) des ersten Elements im zu sortierenden Bereich.
last - ist der Index (Zeiger) des letzten Elements im zu sortierenden Bereich.
Zum Beispiel möchten wir Elemente eines Arrays 'arr' von 1 bis 10 Positionen sortieren, wir werden sort (arr, arr + 10) verwenden und es werden 10 Elemente in aufsteigender Reihenfolge sortiert.
Rückgabewert
Keiner
Komplexität
Der Durchschnitt einer Sortierkomplexität ist N * log2 (N), wobei N = last - first ist.
Datenreichweite
Das Objekt im Bereich [first, last] wird geändert.
Ausnahmen
Die Überladungen mit einem Vorlagenparameter, der als ExecutionPolicy bezeichnet wird, melden Fehler wie folgt:
Wenn der Algorithmus keinen Speicher zuweisen kann, wird std :: bad_alloc als Ausnahme ausgelöst.
Wenn die Ausführung einer Funktion als Teil des Algorithmus aufgerufen wird, wird eine Ausnahme std :: terminate ausgelöst.
Fahren Sie mit diesem Artikel über die Sortierfunktion in C ++ fort
Beispiel - So sortieren Sie Daten in aufsteigender Reihenfolge:
#include using namespace std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (Array) / sizeof (array [0] ) // 'sizeof' gibt die Größe des gesamten Arrays an, dh die Größe jedes Zeichens * Nr. von Zeichen // so um nein zu bekommen. Anzahl der Zeichen // Wir teilen die Größe von (Array) durch die Größe eines beliebigen Zeichens des Arrays // hier ist es Array [0] sort (Array, Array + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Ausgabe :
Erläuterung
Aus dem obigen Beispiel geht hervor, dass die Funktion sort () standardmäßig ein Array in aufsteigender Reihenfolge sortiert.
Hybrid-Framework in Selen-Webdriver
Fahren Sie mit diesem Artikel über die Sortierfunktion in C ++ fort
Beispiel - So sortieren Sie Daten in absteigender Reihenfolge:
Um die Daten des Arrays in absteigender Reihenfolge zu sortieren, müssen wir einen dritten Parameter einführen, mit dem die Reihenfolge angegeben wird, in der die Elemente sortiert werden sollen. Wir können die Funktion 'Greater ()' verwenden, um die Daten in absteigender Reihenfolge zu sortieren.
#include using namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (Array) / sizeof (array [0] ) sort (Array, Array + n, Größer ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Ausgabe:
Exp l eine Nation
Hier führt die Funktion sort () einen Vergleich auf eine Weise durch, bei der ein größeres Element vorangestellt wird.
Fahren Sie mit diesem Artikel über die Sortierfunktion in C ++ fort
Partial_sort
C ++ STL bietet uns eine partielle Sortierfunktion. Die Funktion ähnelt der Funktion sort (), wird jedoch im Gegensatz zur Funktion sort () nicht zum Sortieren des gesamten Bereichs verwendet, sondern nur zum Sortieren eines Teils davon. Es sortiert die Elemente im Bereich von [first, last] so, dass die Elemente vor dem mittleren Element in aufsteigender Reihenfolge sortiert werden, während die Elemente nach dem mittleren Element unverändert bleiben.
Es kann verwendet werden, um das größte Element zu finden, wenn wir ein Funktionsobjekt verwenden, um nach der ersten Position zu sortieren
Beispiel
#include #include #include using Namespace std int main () {Vektor vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr Partial_Sort (vec.begin (), vec.begin () + 1, vec.end (), größer ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Ausgabe:
Erläuterung:
Der obige Code kann verwendet werden, um die größte Zahl in einer Reihe zu finden. Um die kleinste Zahl in Reihe zu finden, müssen wir nur den größeren Befehl entfernen.
Damit sind wir am Ende dieses Artikels über 'Sortierfunktion in C ++' angelangt. Wenn Sie mehr erfahren möchten, lesen Sie das Java-Training von Edureka, einem vertrauenswürdigen Online-Lernunternehmen. Edurekas Der Kurs soll Sie sowohl für Kern- als auch für fortgeschrittene Java-Konzepte sowie für verschiedene Java-Frameworks wie Hibernate & Spring schulen.
Hast du eine Frage an uns? Bitte erwähne es im Kommentarbereich dieses Blogs und wir werden uns so schnell wie möglich bei dir melden.