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.
Pelo que entendi esse algoritmo ajuda realizar a ordenação de um array "quebrando-o" em duas partes a partir do pivô.
Dúvida: em arrays menores teríamos o mesmo resultado apenas aplicando um método de ordenação nativo da linguagem diretamente no array, mas o principal benefício seria realmente reduzir o tempo de processamento em ordenar grandes ou tem mais algum outro benefício em utilizar esse algoritmo?
Ou ainda, por trás do método nativo de ordenação, esse algoritmo é - geralmente - implementado?
Obrigado desde já pela indicação do livro, vou dar uma conferida posteriormente.
cara eu fiquei incredulo agora, nem li todos seus post mas estou lendo este livro e estava buscando auxilio kkk, pelo fato de que algumas coisas no livro estao desconexas kkk slk.. edit: eu como um mero novato na area, sera que estou me precipitando em ler este livro visto que voce com uma bagagem muito a frente esta a ler tambem?
Muito bom, eu tenho um repositório no github onde eu estou colocando tudo que aprendi no livro grokking algorithms em Golang caso queira ver:https://github.com/antunesgabriel/grokking-algorithms
Conhecimento importante que nem todo mundo tem.
Qual a diferença entre o QuickSort e o BubbleSort?
Bem interessante sua explicação, hoje também existe o Quick-Shor In Place que ele não faz a quebra de sub-arrays mas hoje pensando em um array de 10 elementos o metodo bolha claro que é muito mais rápido, mas com uma sentena de milhares esse metodo é extremamente útil.
Um bom adento também seira falar sobre os algoritimos de escolha de pivot como lomuto, hoare e tem um que calcula a média se não me engano
Excelente post, eu tenho uma playlist só sobre esse algoritmo: https://youtube.com/playlist?list=PLtrqXm1wzAovlElffMu7RAjh_EPZPc1tR&si=PxgWU6dcAwK-qM2Q