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.

Tanto o GCC quanto o Clang, compiladores populares para C e C++, implementam suas funções nativas ordenação com uma estratégia que combina quicksort com um algoritmo de ordenação quadrático. A última vez que pesquisei sobre isso o GCC utilziva o insertion sort para arrays menores que 4, enquanto o Clang para arrays com menos de 16 elementos. O quicksort é muito eficiente para arrays maiores devido à sua complexidade média de caso O(nlogn). No entanto, para arrays pequenos, os fatores constantes o tornam menos eficiente do que algoritmos quadráticos mais simples, como o insertion sort, que têm menor custo por itereção e portanto são mais rápidos para conjuntos de dados suficientemente pequenos. E, já que quase todas as linguagens de programação acabam sendo, em algum ponto, um 'wrapper' em torno de C ou C++, é seguro assumir que a maioria das linguagens utiliza essa mesma abordagem para a implementação de suas funções nativas de ordenação.

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?

É um livro fantastico. Eu comecei a ler ele para poder começar a estudar algoritmo e enteder mais sobre programação. Aprendir muita coisas com ele.

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?

Quick sort usa de um "dummy"/pivot para ordenar os arrays puxando tudo que for menor para a esquerda e tudo que foi maior para a direita O bubble sort faz multipla interações pelo array, verificando se um valor (vamos chamar agora de array\[i] é maior que array\[i+1] (o proximo), se o array\[i] é maior que array\[i+1] nos colocamos que array\[i] é array\[i+1] e vice versa. (ou seja, trocamos os dois valores de lugar) um pseudo codigo (em js) ```js // modifica o array function bubble(arr){ while(true){ let sorted = true; for(let i=0;i arr[i+1]){ sorted = false; // gambiarra para trocar os valores [arr[i], arr[i+1]] = [arr[i+1], arr[i]]; } } if(sorted) break; } return arr; } ```

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