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.
Alguns adendos que acho importante serem ditos, até porque quem não tem contato com cursos acadêmicos acaba perdendo.
Para que servem algoritmos de ordenamento?
Para facilitar a resolução de alguns problemas. Por exemplo, como determinar o maior elemento de uma array? E o menor elemento? Se for um array qualquer, você precisará percorrer todo o arranjo para então determinar qual é o elemento, tendo uma complexidade O(n), ou seja, o problema terá um custo cada vez maior ao passo que o tamanho do arranjo aumenta. Contudo, quando falamos de arranjos ordenados, a complexidade se torna O(1), pois sabemos exatamente onde estão os valores, na primeira e última posição.
Outra aplicação é também para algoritmos de busca. Temos dois tipos principais de buscas em um array: busca linear e busca binária. Na busca linear, percorremos todo o arranjo para encontrar ou determinar se um elemento não está no arranjo, trazendo uma complexidade O(n), contudo, em arranjos ordenados, podemos utilizar a busca binária, que resolve o problema com complexidade O(log(n)), que é muito melhor.
Outras formas de implementar o quicksort
O quicksort é um algoritmo recursivo de ordenamento por partição. Isso significa que ele determina duas partições de acordo com o elemento pivô e ordena elas, fazendo isso, recursivamente, até que todo o arranjo esteja ordenado. Segue uma implementação feita em C:
void quicksort(float *A, int size) {
if (size == 2 && A[0] > A[1]) {
int aux = A[0];
A[0] = A[1];
A[1] = aux;
} else if (size > 2) {
int x = A[size / 2];
int i = 0, j = size - 1;
do {
while (A[i] < x)
++i;
while (A[j] > x)
--j;
if (i <= j) {
int aux = A[i];
A[i] = A[j];
A[j] = aux;
++i;
--j;
}
} while (i <= j);
if (j > 0)
quicksort(A, j + 1);
if (i < size)
quicksort(&A[i], size - i);
}
}
Perceba que, ao determinar o elemento pivô (nesse caso é sempre o elemento do meio do arranjo), o algoritmo verifica se existem elementos fora de ordem e, quando os encontra, troca eles de lugar, até que não existam mais nenhum elemento fora de lugar.
Resumindo, ao encontrar um elemento fora de ordem na partição 1 e outro na partição 2, o algoritmo os troca entre si, fazendo assim com que todos os elementos na esquerda do pivô sejam menores que ele e que todos os elementos na sua direita sejam maiores.
Mas há um porém que torna o algoritmo implementado no post ser menos eficiente, que é o fato de que sempre terão duas instâncias recursivas, além de se ter uma maior cópia de memória em cada uma das instâncias (são sempre criados dois arranjos, que somados tem tamanho n-1, o que faz com que seja gasta muita memória desnecessariamente.
O Quicksort tem complexidade O(nlog(n)) em geral, contudo no pior caso, onde todos os elementos se encontram em ordem inversa, tem complexidade O(n²), o que faz com que ele não seja exatamente o melhor algoritmo de ordenamento, mas mesmo assim se tornou o padrão em muitas linguagens.
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