Ähnlich wie Zusammenführen, sortieren Der Quick-Sort-Algorithmus ist ein Divide-and-Conquer-Algorithmus. Zunächst wird ein Element als Pivot-Element ausgewählt und das angegebene Array um den ausgewählten Pivot herum aufgeteilt. Es gibt viele verschiedene Versionen von QuickSort, die Pivot auf unterschiedliche Weise auswählen.
- Wählen Sie immer das erste Element als Pivot (unten implementiert).
- Wählen Sie immer das letzte Element als Drehpunkt.
- Wählen Sie ein zufälliges Element als Drehpunkt.
- Wählen Sie den Median als Pivot.
Der Schlüsselprozess in QuickSort ist der Partition()-Prozess. Das Ziel der Funktion partition() besteht darin, ein Array und ein Element x des Arrays als Pivot zu empfangen, x an der richtigen Position in einem sortierten Array zu platzieren und dann alle kleineren Elemente (kleiner als x) vor x zu platzieren und zu setzen alle größeren Elemente (größer als x) nach x. All dies sollte in linearer Zeit erfolgen, d. h. Big O(n) .
Pseudocode für die rekursive QuickSort-Funktion:
Federmodule
/* low -->Startindex, hoch -> Endindex */ quickSort(arr[], low, high) { if (low Methode-1: CPP // C++-Implementierung des Schnellsortierungsalgorithmus. #include using namespace std; int partition(int arr[], int start, int end) { int plot = arr[start]; int count = 0; for (int i = start + 1; i<= end; i++) { if (arr[i] <= pivot) count++; } // Giving pivot element its correct position int pivotIndex = start + count; swap(arr[pivotIndex], arr[start]); // Sorting left and right parts of the pivot element int i = start, j = end; while (i pivotIndex) { while (arr[i] <= pivot) { i++; } while (arr[j]>Pivot) { j--; } if (i PivotIndex) { swap(arr[i++], arr[j--]); } } return PivotIndex; } void quickSort(int arr[], int start, int end) { // Basisfall if (start>= end) return; // Partitionieren des Arrays int p = partition(arr, start, end); // Den linken Teil sortieren quickSort(arr, start, p - 1); // Den rechten Teil sortieren quickSort(arr, p + 1, end); } int main() { int arr[] = { 9, 3, 4, 2, 1, 8 }; int n = 6; quickSort(arr, 0, n - 1); for (int i = 0; i cout<< arr[i] << ' '; } return 0; } Output 1 2 3 4 8 9 Method-2 : This method’s space complexity is O(n). As we will take an extra array in partition function like in merge function of merge sort . Algorithm explanation and steps of partition function: Make a new array of size equal to given array. push all the smaller elements than pivotElement to the new array. Push pivotElement to new array now. finally, push all the greater elements than pivotElement to the new array. Now, copy the new array to the original array. Store the index of the pivotElement from the original array. Return this index. After this, all the elements in the original array are in the order : smaller than pivotElement ->PivotElement -> größer als PivotElement . Zeitkomplexität: θ(nlogn). Raumkomplexität: O(n). C++ // hinzugefügt von Manish Sharma #include using namespace std; int partition(int* arr, int start, int end) { // Letztes Element als PivotElement annehmen int index = 0, PivotElement = arr[end], PivotIndex; int* temp = new int[end - start + 1]; // Erstellen eines Arrays, dessen Größe dem aktuellen Partitionsbereich entspricht... for (int i = start; i<= end; i++) // pushing all the elements in temp which are smaller than pivotElement { if(arr[i] { temp[index] = arr[i]; index++; } } temp[index] = pivotElement; // pushing pivotElement in temp index++; for (int i = start; i // pushing all the elements in temp which are greater than pivotElement { if(arr[i]>(pivotElement) { temp[index] = arr[i]; index++; } } // alle Elemente jetzt im temporären Array sind order : // Elemente ganz links sind kleiner als PivotElement und Elemente ganz rechts sind größer als PivotElement index = 0; for (int i = start; i<= end; i++) // copying all the elements to original array i.e arr { if(arr[i] == pivotElement) { // for getting pivot index in the original array. // we need the pivotIndex value in the original and not in the temp array pivotIndex = i; } arr[i] = temp[index]; index++; } return pivotIndex; // returning pivotIndex } void quickSort(int* arr, int start, int end) { if(start { int partitionIndex = partition(arr, start, end); // for getting partition quickSort(arr, start, partitionIndex - 1); // sorting left side array quickSort(arr, partitionIndex + 1, end); // sorting right side array } return; } int main() { int size = 9; int arr[size] = {5, 12, 7, 1, 13, 2 ,23, 11, 18}; cout << 'Unsorted array : '; for (int i = 0; i { cout << arr[i] << ' '; } printf('
'); quickSort(arr, 0, size - 1); cout << 'Sorted array : '; for (int i = 0; i { cout << arr[i] << ' '; } return 0; } Output Unsorted array : 5 12 7 1 13 2 23 11 18 Sorted array : 1 2 5 7 11 12 13 18 23 Please refer complete article on QuickSort for more details!>