O que é Quicksort?

O Quicksort é um dos algoritmos de classificação eficientes. O algoritmo executa a classificação aplicando o paradigma de divisão e conquista. Considere uma matriz A [1… n] de n elementos. O algoritmo divide a matriz A em um índice q, de modo que todos os elementos da sub-matriz à esquerda do índice sejam menores que o elemento no índice q (a [q]), e todos os elementos na subarray direita são maiores que um [Q]. Agora, o algoritmo classifica recursivamente os dois subarra um [1… q-1] e um [q+1… n] no local chamando a função do Quicksort. Para obter o índice q, o algoritmo usa uma função de partição.

A função de partição é uma função que leva uma matriz a [l… u] como entrada. Aqui, eu é o limite inferior e você é o limite superior da matriz. O algoritmo encontra um índice q de modo que todos os elementos menos que um [q] caem na subarray a [l… q-1], e todos os elementos maiores que um [q] caem na subarray a [q+1… u]. A função de partição alcança isso usando um elemento dinâmico e dois ponteiros - ponteiro I e ponteiro j para a matriz.

Ponteiro J aponta para o primeiro elemento da matriz, e o ponteiro I é inicializado como J-1. A função itera através da matriz usando o ponteiro j. Para o elemento A [j], o elemento pode ser maior que o elemento dinâmico ou menor que o elemento pivô. Se o elemento for maior que o elemento pivô, o ponteiro J ficará incrementado, apontando para o próximo elemento. Se o elemento a [j] for menor que o elemento pivô, incrementamos o ponteiro I, trocamos um [i] e um [j]. A troca dos elementos ajuda. Como uma etapa final, a função de partição troca o elemento pivô com o elemento no índice I+1, movendo assim o elemento pivô na posição correta na matriz particionada.

Código fonte

Def Partition (arr, lb, ub):
# O último elemento da matriz é levado
# para ser elemento pivô
pivot_elt = arr [ub-1]
i = lb - 1
para j em range (lb, ub):
# Se o elemento for menor que o elemento pivô
Se arr [j] # Troque os elementos para que os elementos
# arr [lb… i] é sempre menor que elemento pivô
i = i + 1
arr [i], arr [j] = arr [j], arr [i]
# Troca final do elemento pivô e arr [i+1]
# para colocar o elemento dinâmico
arr [i+1], arr [ub-1] = arr [ub-1], arr [i+1]
retornar i+1
def Quick_Sort (arr, lb, ub):
if (lb# Classificando recursivamente a matriz
q = partição (arr, lb, ub)
arr = Quick_sort (arr, lb, q)
arr = Quick_sort (arr, q+1, ub)
retornar arr
Se __name__ == "__main__":
arr = [3, 7, 9, 2, 5, 0]
n = len (arr)
arr = Quick_sort (arr, 0, n)
Imprimir (arr)

A melhor complexidade do tempo do Quicksort é O (n log n). No cenário de melhor caso, em cada chamada para o algoritmo, o algoritmo divide o problema em dois subproblemas de tamanho igual. A pior complexidade do tempo do algoritmo Quicksort é O (n^2). Isso ocorre quando o elemento de partição é sempre escolhido como o último elemento, e a matriz já está classificada.