Der folgende Artikel enthält einen Überblick über C++ QuickSort. In der Programmiersprache brauchen wir immer Algorithmen, um sie effizient zu machen, und Quicksort ist einer davon. Wie der Name schon sagt, wird es verwendet, um die Elemente zu sortieren. Es folgen einige Schritte, um dies zu tun. Dieser Algorithmus wählt ein Element aus der Liste aus, das als „Pivot“ bekannt ist, und teilt die Liste wiederum in zwei Teile, um eine effektive Sortierung zu ermöglichen.
Syntax von C++ QuickSort
Da es sich um einen Algorithmus handelt, hat er keine Syntax, aber er definiert einen Schritt, der befolgt werden muss, während die schnelle Sortierung in einer beliebigen Sprache implementiert wird.
Starten Sie Ihren kostenlosen Softwareentwicklungskurs
Webentwicklung, Programmiersprachen, Softwaretests und andere
- Schritt A: Wählen Sie ein Element aus der Liste als Pivot.
- Schritt B: Wählen Sie zwei Elemente als links und rechts aus.
- Schritt C: Das linke Element repräsentiert einen niedrigen Index.
- Schritt D: Das rechte Element repräsentiert einen hohen Index.
- Schritt E: Wenn der Wert links kleiner ist, nach rechts gehen.
- Schritt F: Wenn der Wert rechts höher ist, bewegen Sie sich nach links.
Wir führen diese Schritte durch, bis die kleineren und größeren Elemente aneinander vorbeikommen.
Indem wir also die obigen Schritte befolgen, können wir dies unseren Code in der Sprache C++ implementieren. Aber die Grundidee dahinter wäre für alle Sprachen gleich.
Wie QuickSort in C++ mit Algorithmus funktioniert
Wie wir jetzt wissen, wird QuickSort verwendet, um das Element auf effiziente Weise zu sortieren. Es ist ein Algorithmus, der einige Schritte definiert, die befolgt werden müssen, um dies im Code zu implementieren. Dieser Algorithmus arbeitet grundsätzlich mit Pivot-Elementen, er nimmt ein Element aus der Liste als Pivot und teilt die gesamte Liste in zwei Unterlisten und sortiert sie.
Wir können das Pivot-Element auf verschiedene Arten wählen, die unten definiert sind:
- Wir können das letzte Element als Pivot-Element nehmen.
- Wir können das mittlere Element als Pivot-Element nehmen.
- Wir können das erste Element als Pivot-Element nehmen.
- Wir können jedes zufällige Element als Pivot-Element nehmen.
Wir können jedem der Ansätze folgen, die unsere Elementliste weiter in zwei verschiedene Unterlisten aufteilen. Wir werden die anderen Elemente in das Array oder die Liste nach links und rechts verschieben, um sie zu sortieren.
Unten sehen wir einen einfachen Algorithmus, der verwendet wird, um QuickSort in der Sprache C++ zu definieren.
Algorithmus:
quickSorAlgo(Array, weniger, mehr)
//Algologik starten
beginnen
Hier definieren wir ein Array, das sortiert werden muss
weniger =erstes Element;
more =letztes Element;
schwenken
if(less
//Sortierlogik starten
beginnen
pivot =partitionList (Array,weniger,mehr);
quickSorAlgo(Array,less,pivot-1)
quickSorAlgo(Array,pivot+1,more)
//hier endet es
Ende
//Algorithmus endet
Ende
Lassen Sie uns den Algorithmus im Detail verstehen:
50, 25, 15, 20, 60, 30.
Betrachten Sie das obige Array, das verschiedene Elemente enthält. Wir wählen hier das Pivot-Element als letztes Element aus und haben dementsprechend das erste Element des Arrays als niedrig und das letzte Element des Arrays als hoch markiert. Jetzt werden wir unsere Zeiger zu den jeweiligen Positionen iterieren, aber dafür werden wir einer Regel folgen, um die Elemente zu vergleichen.
Wenn das markierte Element hoch kleiner als unser ausgewähltes Pivot-Element ist und das niedrig markierte Element größer als unser Pivot-Element ist, werden wir in diesem Fall die Tränke des Elements miteinander austauschen und die Positionen unserer jeweiligen Elemente ebenfalls erhöhen sie sollen zeigen. Wir werden diese Iteration fortsetzen, bis sich unser niedriges und hohes Element kreuzen und das Pivot-Element an der richtigen Position ist, wo es sein sollte, dies wird das Array oder die Liste in zwei Unterlisten teilen, diese beiden Listen können mit QuickSort sortiert werden Algorithmus unabhängig.
15, 20, 25, 30, 50, 60
Die endgültige Ausgabe des obigen Sortieralgorithmus wäre also dies. Wir können unsere Arrays einfach und effektiv sortieren, indem wir den QuickSort-Algorithmus in C++ verwenden.
Punkte, die Sie beim Arbeiten mit QuickSort beachten sollten:
Worst-Case: O (n 2 )
Durchschnittsfall: O (n log n)
Bester Fall: O (n log n)
In diesem Beispiel sortieren wir Array-Elemente mit Quick Sort und betrachten das Pivot-Element als letztes Element des Arrays.
Code:
Ausgabe:
Durch die Verwendung des QuickSort-Algorithmus können wir unsere Array-Listenelemente effizient sortieren. Wir müssen nur das Pivot-Element auswählen, um damit fortzufahren. Dadurch wird das Array oder die Liste in zwei Teile geteilt, dann können wir den QuickSort-Algorithmus rekursiv ausführen, um die sortierte Elementliste zu erhalten.
Beispiel für C++ QuickSort
#include <iostream>
using namespace std;
void elementSwap(int* ele1, int* ele2)
{
int temp = *ele1;
*ele1 = *ele2;
*ele2 = temp;
}
int elementPartition (int array[], int less, int more)
{
int pivotelement = array[more];
int indexSmaller = (less - 1);
for (int qs = less; qs <= more - 1; qs++)
{
if (array[qs] < pivotelement)
{
indexSmaller++;
elementSwap(&array[indexSmaller], &array[qs]);
}
}
elementSwap(&array[indexSmaller + 1], &array[more]);
return (indexSmaller + 1);
}
void demoquickSort(int array[], int less, int greater)
{
if (less < greater)
{
int parInd = elementPartition(array, less, greater);
demoquickSort(array, less, parInd - 1);
demoquickSort(array, parInd + 1, greater);
}
}
int main()
{
cout << "Sorting array elemnts using quick sort in C++ ::** \n";
int array[] = {35, 15, 90, 26, 87, 12, 5, 44, 23, 1};
int arrsize = sizeof(array) / sizeof(array[0]);
cout << "Before sort array is : \n";
int z;
for (z = 0; z < arrsize; z++)
cout << array[z] << " ";
cout << endl;
demoquickSort(array, 0, arrsize - 1);
cout << "After sorted array is : \n";
int i;
for (i = 0; i < arrsize; i++)
cout << array[i] << " ";
cout << endl;
return 0;
}Schlussfolgerung