Leia isso em outros idiomas: 简体中文, English
Quicksort é um algoritmo de dividir para conquistar. Quicksort primeiro divide uma grande matriz em duas menores submatrizes: os elementos baixos e os elementos altos. O Quicksort pode então classificar recursivamente as submatrizes.
As etapas são:
- Escolha um elemento, denominado pivô, na matriz.
- Particionamento: reordene a matriz para que todos os elementos com valores menores que o pivô estejam antes do pivô, enquanto todos elementos com valores maiores do que o pivô vêm depois dele (valores iguais podem ser usados em qualquer direção). Após este particionamento, o pivô está em sua posição final. Isso é chamado de operação de partição.
- Aplique recursivamente as etapas acima à submatriz de elementos com valores menores e separadamente para o submatriz de elementos com valores maiores.
Visualização animada do algoritmo quicksort. As linhas horizontais são valores dinâmicos.
| Nome | Melhor | Média | Pior | Memória | Estável | Comentários |
|---|---|---|---|---|---|---|
| Quick sort | n log(n) | n log(n) | n2 | log(n) | Não | Quicksort geralmente é feito no local com espaço de pilha O(log(n)) |