Algoritmo Quicksort: como implementar em Python

Seguiremos os seguintes passos para chegar ao nosso objetivo:

1. Escolheremos um pivô (no caso, o primeiro item da lista) e vamos trocá-lo de posição com o item do meio;
2. Vamos percorrer toda a lista e verificar item a item, comparando-os com o pivô. A partir de então:

• Caso o item esteja numa posição menor do que o pivô pela ordem alfabética, será transferido ou mantido à lista da esquerda;
• Caso o item esteja numa posição maior do que o pivô pela ordem alfabética, será transferido ou mantido à lista da direita.

Fazendo isso de forma recursiva, ao final teremos uma lista ordenada

Vamos implementar?

Notamos que o desempenho com o qual o QuickSort executou é bem similar ao do MergeSort, não é? E quanto a complexidade? Vamos compará-los?

Como no MergeSort, nós dividimos a lista recursivamente, mas não necessariamente ao meio e sim a partir de um pivô. Isso nos lembra a notação O(lg N), certo? Certo!

Além disso, devemos considerar que, a cada chamada recursiva, percorremos toda a lista para garantir que todos os alunos cujos nomes estejam numa posição menor do que o pivô na ordem alfabética encontrem-se à sua esquerda. Já os alunos com nomes em posições maiores do que o pivô na ordem alfabética, devem estar à sua direita (como é mostrado na imagem abaixo), o que nos lembra um algoritmo linear, certo? Mais uma vez, certíssimo. Então podemos determinar que isso nos dá a complexidade O(N lg N) assim como no MergeSort.

Agora, será que em qualquer cenário o algoritmo QuickSort executa em O(N lg N)? Quais seriam as diferenças de eficiência entre o QuickSort e MergeSort, visto que aparentam sempre ter a mesma complexidade? Qual é o melhor algoritmo?

Explicamos de forma mais aprofundada essa comparação entre os algoritmos QuickSort e MergeSort depois de entender melhor sobre a Notação BigO.