Implementation (Part 2)
Leçon 6 sur 9 du cours Quick Sort - Série DSA de Coddy.
Maintenant, nous combinons le pivot, le partitionnement et la récursion dans l'algorithme complet.
Défi
FacileMaintenant, rassemblez tout cela pour former l'algorithme complet.
Écrivez une fonction nommée quickSort qui prend un tableau d'entiers et le renvoie trié par ordre croissant.
Utilisez le dernier élément comme pivot, partitionnez le reste en un groupe plus petit et un groupe plus grand, appliquez récursivement quickSort à chaque groupe, et combinez-les sous la forme plus-petits-triés + pivot + plus-grands-triés. Un tableau de 0 ou 1 élément est déjà trié, renvoyez-le donc tel quel.
Vous pouvez réutiliser l'idée de partition de la leçon précédente.
Essayez vous-même
#include <stdlib.h>
int* quickSort(int* arr, int arr_size, int* returnSize) {
// Écrivez le code ici
*returnSize = arr_size;
return arr;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Quick Sort - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity