Guia do algoritmo Python Quicksort
Explore o algoritmo quicksort em Python. Aprenda seleção dinâmica, particionamento e recursão neste exemplo de codificação interativo.
Visão geral
Quicksort é um algoritmo de classificação extremamente rápido e amplamente utilizado. Assim como a classificação por mesclagem, ela emprega uma abordagem de dividir e conquistar. No entanto, o quicksort classifica os elementos 'no local', tornando-o eficiente em termos de memória.
O algoritmo funciona selecionando um elemento 'pivô' da lista. Em seguida, ele divide os outros elementos em duas submatrizes: aqueles menores que o pivô e aqueles maiores que o pivô. Este processo é aplicado recursivamente às submatrizes.
Embora o Quicksort tenha uma complexidade de pior caso de O(n²), seu tempo de execução de caso médio é O(n log n) e normalmente supera a classificação por mesclagem na prática devido a menores perdas de cache e sobrecarga zero na criação de matrizes temporárias.
Saída de código e execução
Um script recursivo conciso de classificação rápida usando compreensão de lista para alta legibilidade.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Implementação passo a passo
- Rotinas de classificação do sistema onde o consumo de memória deve ser mantido no mínimo
- Classificação de uso geral em estruturas de biblioteca de linguagem padrão
- Ensino acadêmico de mecânica de partição e divisão e conquista recursiva
Perguntas frequentes
Como podemos evitar a complexidade do pior caso de O(n²) no Quicksort?
O pior caso ocorre quando o pivô selecionado é repetidamente o menor ou o maior elemento. Para mitigar isso, os desenvolvedores usam estratégias como escolher um pivô aleatório ou os valores “mediana de três”.
O Quicksort é estável?
Não, o Quicksort padrão é instável. Durante o particionamento, os elementos são trocados em longos intervalos, o que pode alterar a ordem relativa dos elementos duplicados.
Tópicos Relacionados
Aprenda como implementar Merge Sort em Python. Um exemplo interativo passo a passo da estratégia de classificação Dividir e Conquistar.
Algoritmos de classificação PythonExplore algoritmos de classificação python. Visualize a classificação por bolha e a classificação por mesclagem nativamente em um contexto IDE do navegador.
Algoritmo de pesquisa binária PythonPesquise listas classificadas em tempo logarítmico O (log n). Execute e entenda a pesquisa binária em Python, incluindo lógica passo a passo, casos extremos e otimizações.