 |
|
Você está aqui: Python ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
|
Como implementar a ordenação Quicksort em Python - Apostila de Python para iniciantesQuantidade de visualizações: 379 vezes |
|
|
A ordenação Quicksort é um dos algorítmos de ordenação mais encontrados em aplicações reais de programação. No Delphi esta ordenação é encontrada no objeto TList. No Java podemos encontrá-lo no método Arrays.sort(). Na linguagem C a ordenação Quicksort é implementada na função qsort() da biblioteca padrão. O algoritmo de ordenação Quicksort é do tipo dividir para conquistar (divide-and-conquer principle). Neste tipo de algoritmo o problema é dividido em sub-problemas e a solução é concatenada quando as chamadas recursivas atingirem o caso base. O vetor (ou array) a ser ordenado é dividido em duas sub-listas por um elemento chamado pivô, resultando em uma lista com elementos menores que o pivô e outra lista com os elementos maiores que o pivô. Esse processo é repetido para cada chamada recursiva. Sim, a ordenação Quicksort faz uso extensivo de recursividade, razão pela qual devemos ter muito cuidado para não estourar a pilha do sistema. Existem muitos estudos sobre o pivô ideal para a ordenação Quicksort. Nessa dica adotarei o último elemento do array ou sub-array como pivô. Em vetores não ordenados essa estratégia, em geral, resulta em uma boa escolha. Vamos ao código Python então? Veja um programa Python completo demonstrando o uso da ordenação Quicksort para um array de 10 elementos inteiros:
Ao executar este código Python nós teremos o seguinte resultado: Informe o valor do elemento 0: 7 Informe o valor do elemento 1: 2 Informe o valor do elemento 2: 43 Informe o valor do elemento 3: 1 Informe o valor do elemento 4: 9 Informe o valor do elemento 5: 6 Informe o valor do elemento 6: 22 Informe o valor do elemento 7: 3 Informe o valor do elemento 8: 37 Informe o valor do elemento 9: 5 O array informado foi: 7 2 43 1 9 6 22 3 37 5 O array ordenado é: 1 2 3 5 6 7 9 22 37 43 |
|
 Link para compartilhar na Internet ou com seus amigos: |
|
Desafios, Exercícios e Algoritmos Resolvidos de Python |
Veja mais Dicas e truques de Python |
Dicas e truques de outras linguagens |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |
