Implementation (Part 1)
Lektion 5 von 9 im Kurs Quick Sort - DSA-Serie von Coddy.
Wir werden Quicksort ausgehend von seiner Kernoperation aufbauen.
Aufgabe
EinfachDas Herzstück von Quick Sort ist der partition-Schritt. Lassen Sie uns diesen zuerst bauen.
Schreiben Sie eine Funktion namens partition, die das letzte Element von arr als Pivot verwendet und ein neues Array zurückgibt mit:
- allen Elementen, die kleiner als das Pivot sind (in ihrer ursprünglichen Reihenfolge),
- dann dem Pivot,
- dann allen verbleibenden Elementen, also jenen, die größer oder gleich dem Pivot sind (in ihrer ursprünglichen Reihenfolge).
Zum Beispiel wird [3, 7, 1, 8, 5] zu [3, 1, 5, 7, 8] (Pivot 5).
Probier es selbst
#include <stdlib.h>
int* partition(int* arr, int arr_size, int* returnSize) {
// Hier Code schreiben
*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