Quicksort
Escolhe um valor, o pivô, e põe os valores menores à esquerda dele e os maiores à direita. Depois faz o mesmo em cada lado.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- não
- sim
Melhor caso: como o tempo cresce com o tamanho n da lista quando a entrada é a mais fácil para este algoritmo.
Caso médio: como o tempo costuma crescer com n. Com n², o dobro de valores demora cerca de quatro vezes mais; n log n cresce bem menos.
Pior caso: o crescimento com a entrada mais difícil. Útil quando a velocidade nunca pode cair.
Memória: quanta memória extra é necessária além da lista. 1 significa algumas variáveis; n, uma cópia da lista.
Estável: dois valores iguais mantêm a ordem original. Importa quando se ordena por um só campo de um registo.
Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- a comparar
- a mover
- pivô
- na posição final
Profundidade da recursão: 0 · mínima possível: 4 · pior caso: 23 à espera do seu pivô
Carregue em Reproduzir: as linhas mostram como o custo cresce
Carregue em Reproduzir ou avance passo a passo pelo algoritmo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
Experimente: Escolha uma lista invertida. O pivô é sempre o menor ou o maior valor restante, por isso um dos lados fica vazio e o custo sobe para n².
Como funciona
Aqui o pivô é o último valor do intervalo. Da esquerda para a direita, cada valor que não seja maior do que o pivô é trocado para o lado esquerdo. Depois o pivô vai para o meio dos dois lados, onde fica de vez. Cada lado é ordenado da mesma maneira.
Quando é uma boa escolha
Uma das formas mais rápidas de ordenar na prática, e quase não precisa de memória extra. Mas se escolher sempre um mau pivô, por exemplo numa lista já ordenada, fica lento. As versões reais escolhem o pivô com mais cuidado.