Implementation (Part 1)
Lição 5 de 9 do curso Quick Sort - Série DSA da Coddy.
Nós construiremos o Quick Sort a partir de sua operação principal.
Desafio
FácilO coração do Quick Sort é a etapa de partição (partition). Vamos construir isso primeiro.
Escreva uma função chamada partition que use o último elemento de arr como o pivô e retorne um novo array com:
- todos os elementos menores que o pivô (em sua ordem original),
- depois o pivô,
- depois todos os elementos restantes, aqueles maiores ou iguais a o pivô (em sua ordem original).
Por exemplo, [3, 7, 1, 8, 5] torna-se [3, 1, 5, 7, 8] (pivô 5).
Experimente você mesmo
#include <stdlib.h>
int* partition(int* arr, int arr_size, int* returnSize) {
// Escreva o código aqui
*returnSize = arr_size;
return arr;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Quick Sort - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity