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.

Posts anteriores

• Algoritmo de ordenação por seleção
• Algoritmo de busca binária - Binary Search

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.