Algoritmo de ordenação - Quicksort
No meu último post no TabNews, eu falei sobre o algoritmo de ordenação por seleção. Continuando essa jornada através dos algoritmos, hoje vou falar sobre o Quicksort, que tem uma eficiência maior em comparação com o método de ordenação por seleção.
ps: esse post foi baseado na minha leitura do livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos, caso queira se aprofundar melhor e entender mais sobre, indico muito a leitura.
O Quicksort é um algoritmo de ordenação extremamente útil para arrays desordenados. Seu funcionamento baseia-se na divisão do array em dois subarrays, utilizando um pivô (elemento central) como referência. Este pivô é escolhido para criar subarrays menores e maiores em relação a ele.
Mas como funciona?
Considere o seguinte cenário ao ordenar o array [14,6,5,20,2]:
-
Em primeiro lugar, precisamos verificar se o array possui um ou nenhum elemento, pois arrays com 1 ou nenhum elemento não precisam ser ordenados.
-
Se o array tiver mais de um elemento, escolhemos um elemento como pivô. Neste caso, o pivô seria [14].
-
Em seguida, identificamos os elementos menores e maiores que o pivô (14):
- Elementos menores que 14: [6,5,2]
- Elementos maiores que 14: [20]
-
Para ordenar os subarrays menores e maiores, utilizamos uma função recursiva, repetindo o processo até que cada subarray contenha apenas um elemento. No final, basta concatenar o array menor, o pivô e o array maior.
qsort([5,6,2]) + [pivot] + qsort([20])Resultando em: [2,5,6,14,20]
ilustração:
código fonte:
array = [14,6,5,20,2]
def qsort(array):
if len(array) < 2:
return array
pivot = array[0]
left = [i for i in array[1:] if i <= pivot]
right = [i for i in array[1:] if i > pivot]
return qsort(left) + [pivot] + qsort(right)
print(f'original array: {array}') # out: [14,6,5,20,2]
print(f'ordered array: {qsort(array)}') # out: [2,5,6,14,20]
analisando o código fonte
- Em primeiro lugar, vamos verificar se o array que queremos ordenar é menor que 2, se o array tiver so 1 ou nenhum elemento, não será preciso ordená-lo.
if len(array) < 2:
return array
- Nessa parte é criado os subarrays que vai conter o elementos menores e maiores que o pivô. Observe que, dentro do loop for, é excluído o primeiro elemento, já que ele é o elemento central e não é essencial para a formação dos novos arrays. Essa exclusão otimiza o processo de criação dos subarrays, pois o pivô já está sendo considerado como elemento central.
left = [i for i in array[1:] if i <= pivot]
right = [i for i in array[1:] if i > pivot]
-
Essa linha de código representa a etapa de combinação na implementação do algoritmo de ordenação rápida (quicksort) de forma recursiva.
-
qsort(left): Chama recursivamente a função qsort para ordenar o subarray left, que contém elementos menores ou iguais ao pivô. -
[pivot]: Representa o pivô atual. -
qsort(right): Chama recursivamente a função qsort para ordenar o subarray right, que contém elementos maiores que o pivô.
Portanto, a função qsort está ordenando de forma recursiva os subarrays à esquerda e à direita do pivô e, em seguida, combinando-os na ordem correta: left, seguido pelo pivô e, finalmente, right. Esse processo é repetido até que todos os subarrays tenham tamanho zero ou um (caso base da recursão), e a lista completa seja ordenada.
-
return qsort(left) + [pivot] + qsort(right)
Este post teve uma referência do livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos, no qual estou me baseando. Qualquer dúvida, sinta-se à vontade para comentar; responderei com o maior prazer.