Implementation (Part 2)
Lição 6 de 9 do curso Quick Sort - Série DSA da Coddy.
Agora combinamos o pivô, a partição e a recursão no algoritmo completo.
Desafio
FácilAgora junte tudo no algoritmo completo.
Escreva uma função chamada quickSort que recebe um array de inteiros e o retorna ordenado em ordem crescente.
Use o último elemento como o pivô, particione o restante em um grupo menor e um grupo maior, chame recursivamente quickSort para cada grupo e combine-os como menores-ordenados + pivô + maiores-ordenados. Um array com 0 ou 1 elementos já está ordenado, então retorne-o como está.
Você pode reutilizar a ideia de partição da lição anterior.
Experimente você mesmo
#include <stdlib.h>
int* quickSort(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