Implementation (Part 1)
Leçon 5 sur 9 du cours Quick Sort - Série DSA de Coddy.
Nous allons construire le tri rapide à partir de son opération de base.
Défi
FacileLe cœur du Quick Sort est l'étape de partition. Commençons par construire cela.
Écrivez une fonction nommée partition qui utilise le dernier élément de arr comme pivot et renvoie un nouveau tableau avec :
- tous les éléments inférieurs au pivot (dans leur ordre d'origine),
- puis le pivot,
- puis tous les éléments restants, ceux supérieurs ou égaux au pivot (dans leur ordre d'origine).
Par exemple, [3, 7, 1, 8, 5] devient [3, 1, 5, 7, 8] (pivot 5).
Essayez vous-même
#include <stdlib.h>
int* partition(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