Implementation (Part 2)
Lektion 6 von 9 im Kurs Quick Sort - DSA-Serie von Coddy.
Nun kombinieren wir Pivot, Partitionierung und Rekursion zum vollständigen Algorithmus.
Aufgabe
EinfachFügen Sie nun alles zum vollständigen Algorithmus zusammen.
Schreiben Sie eine Funktion namens quickSort, die ein Ganzzahl-Array entgegennimmt und dieses in aufsteigender Reihenfolge sortiert zurückgibt.
Verwenden Sie das letzte Element als Pivot, partitionieren Sie den Rest in eine kleinere und eine größere Gruppe, führen Sie quickSort rekursiv für jede Gruppe aus und kombinieren Sie diese als sortiert-kleiner + Pivot + sortiert-größer. Ein Array mit 0 oder 1 Elementen ist bereits sortiert, geben Sie es also unverändert zurück.
Sie können die Partitionierungsidee aus der vorherigen Lektion wiederverwenden.
Probier es selbst
#include <stdlib.h>
int* quickSort(int* arr, int arr_size, int* returnSize) {
// Schreibe den Code hier
*returnSize = arr_size;
return arr;
}
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Quick Sort - DSA-Serie
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity