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: 326 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: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # função principal do programa def main(): # vamos declarar um array de 10 elementos valores = [0 for x in range(10)] # vamos pedir ao usuário para informar os valores para o vetor for i in range(0, len(valores)): valores[i] = int(input("Informe o valor do elemento {0}: ".format(i))) # vamos mostrar o array informado print("\nO array informado foi:\n") for i in range(0, len(valores)): print(valores[i], end=" ") # vamos ordenar o vetor usando a ordenação Quicksort quick_sort(valores, 0, len(valores) - 1) print("\n\nO array ordenado é:\n") for i in range(0, len(valores)): print(valores[i], end=" ") print("\n\n") # função de implementação da ordenação Quicksort def quick_sort(vetor, inicio, fim): # o início é menor que o fim? if inicio < fim: # vamos obter o novo índice da partição indice_particao = particionar(vetor, inicio, fim) # efetuamos novas chamadas recursivas quick_sort(vetor, inicio, indice_particao - 1) quick_sort(vetor, indice_particao + 1, fim) # função que retorna o índice de partição def particionar(vetor, inicio, fim): # para guardar o pivô pivot = vetor[fim] i = (inicio - 1) for j in range(inicio, fim): if vetor[j] <= pivot: i = i + 1 # fazemos a troca temp = vetor[i] vetor[i] = vetor[j] vetor[j] = temp # efetua a troca temp = vetor[i + 1] vetor[i + 1] = vetor[fim] vetor[fim] = temp return i + 1 if __name__== "__main__": main() 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: |
Python ::: NumPy Python Library (Biblioteca Python NumPy) ::: Matemática e Estatística |
Tutorial Machine Learning com Python - Como usar o método mean() da biblioteca NumPy para calcular média (ou média aritmética simples)Quantidade de visualizações: 3787 vezes |
Média aritmética (ou simplesmente média simples) é a soma de vários valores e dividido pelo total deles. Ou seja, o resultado dessa divisão equivale a um valor médio entre todos os valores. Veja a seguinte figura: Veja que temos 4 valores: 4, 9, 12 e 25. Assim, para obter a média aritmética desses valores, só precisamos somá-los e depois dividir pela quantidade, ou seja, por 4. A média resultante será 12,5. A biblioteca NumPy do Python nos oferece o método mean(), muito usado em Data Science e Machine Learning, que recebe um vetor de valores númericos (inteiro ou decimais) e retorna a média deles. Veja um exemplo: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # importamos a biblioteca NumPy import numpy def main(): # valores a serem observados valores = [4, 9, 12, 25] # vamos obter a média aritmética simples media = numpy.mean(valores) # vamos mostrar o resultado print("A média dos valores é:", media) if __name__== "__main__": main() Ao executarmos este código nós teremos o seguinte resultado: A média dos valores é: 12.5 |
Python ::: Estruturas de Dados ::: Lista Ligada Simples |
Como excluir um nó no final de uma lista encadeada simples em PythonQuantidade de visualizações: 1081 vezes |
Nesta dica mostrarei como podemos escrever um método remover_final() que remove e retorna o nó no final de uma lista encadeada simples em Python, ou seja, excluí o último nó da lista. É importante observar que o método exclui o último nó e o retorna completo, inclui o valor que está incluído nele. Se a lista estiver vazia o método retorna o valor None para indicar lista vazia. Vamos começar então com o código para a classe No da lista singularmente ligada (que salvei em um arquivo no_lista_singularmente_ligada.py): ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # classe No para uma lista singularmente encadeada ou # ligada - Singly Linked List class No: # construtor da classe No def __init__(self, info, proximo): self.info = info self.proximo = proximo # método que permite definir o conteúdo do nó def set_info(self, info): self.info = info # método que permite obter a informação de um nó def get_info(self): return self.info # método que permite definir o campo próximo deste nó def set_proximo(self, proximo): self.proximo = proximo # método que permite obter o campo próximo deste nó def get_proximo(self): return self.proximo # retorna True se este nó apontar para outro nó def possui_proximo(self): return self.proximo != None Veja que o código para a classe Nó não possui muitas firulas. Temos apenas um campo info, que guardará o valor do nó, e um campo próximo, que aponta para o próximo nó da lista, ou null, se este for o único nó ou o último nó da lista ligada. Veja agora o código para a classe ListaLigadaSimples (lista_ligada_simples.py), com os métodos inserir_inicio(), remover_final() e exibir(): ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # importa a classe No from no_lista_singularmente_ligada import No # classe ListaLigadaSimples class ListaLigadaSimples: # construtor da classe def __init__(self): self.inicio = None # nó inicial da lista # método que deleta um nó no final de uma lista ligada # este método retorna o nó excluído def remover_final(self): # a lista está vazia? if self.inicio == None: return None else: # vamos excluir e retornar o primeiro nó da lista removido = self.inicio # a lista possui apenas um nó? if self.inicio.get_proximo() == None: # a lista agora ficará vazia self.inicio = None else: # começamos apontando para o início da lista no_atual = self.inicio no_anterior = self.inicio # enquanto o próximo do nó atual for diferente de nulo while no_atual.get_proximo() != None: # avançamos o nó anterior no_anterior = no_atual # saltamos para o próximo nó no_atual = no_atual.get_proximo() # na estamos na posição de exclusão removido = no_atual no_anterior.set_proximo(None) # retorna o nó removido return removido # método que permite inserir um novo nó no início da lista def inserir_inicio(self, info): # cria um novo nó contendo a informação e que # não aponta para nenhum outro nó novo_no = No(info, None) # a lista ainda está vazia? if self.inicio == None: # o novo nó será o início da lista self.inicio = novo_no else: # o novo nó aponta para o início da lista novo_no.set_proximo(self.inicio) # o novo nó passa a ser o início da lista self.inicio = novo_no # método que permite exibir todos os nós da lista # ligada simples (lista singularmente encadeada) def exibir(self): # aponta para o início da lista no_atual = self.inicio # enquanto o nó não for nulo while no_atual != None: # exibe o conteúdo do nó atual print(no_atual.get_info()) # pula para o próximo nó no_atual = no_atual.get_proximo() E agora o código main() que insere alguns valores no início da nossa lista singularmente encadeada e testa o método remover_final(): ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # importa a classe ListaLigadaSimples from lista_singularmente_ligada import ListaLigadaSimples # método principal def main(): # cria uma nova lista encadeada simples lista = ListaLigadaSimples() print("Insere o valor 12 no início da lista") lista.inserir_inicio(12) print("Conteúdo da lista: ") lista.exibir() print("Insere o valor 30 no início da lista") lista.inserir_inicio(30) print("Conteúdo da lista: ") lista.exibir() print("Insere o valor 27 no início da lista") lista.inserir_inicio(27) print("Conteúdo da lista: ") lista.exibir() print("Remove um nó no final da lista") removido = lista.remover_final() if removido == None: print("Não foi possível remover. Lista vazia") else: print("Nó removido:", removido.get_info()) print("Conteúdo da lista: ") lista.exibir() if __name__== "__main__": main() Ao executar este código Python nós teremos o seguinte resultado: c:\estudos_python>python estudos.py Insere o valor 12 no início da lista Conteúdo da lista: 12 Insere o valor 30 no início da lista Conteúdo da lista: 30 12 Insere o valor 27 no início da lista Conteúdo da lista: 27 30 12 Remove um nó no final da lista Nó removido: 12 Conteúdo da lista: 27 30 |
Python ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes) |
Exercício Resolvido de Python - Como percorrer todos os elementos de um vetor de inteiros e exibir a soma de seus valoresQuantidade de visualizações: 804 vezes |
Pergunta/Tarefa: Considere o seguinte vetor de inteiros: // um vetor de inteiros contendo sete elementos valores = [4, 5, 1, 8, 2, 2, 10] A soma dos valores do vetor é: 32 Resposta/Solução: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # método principal def main(): # um vetor de inteiros contendo sete elementos valores = [4, 5, 1, 8, 2, 2, 10] # o primeiro passo é criar uma variável que vai receber a soma # dos valores dos elementos soma = 0 # agora vamos usar uma laço for para percorrer todos os elementos # do vetor, obter o valor do elemento atual e adicionar ao valor atual # da variável soma for valor in valores: soma = soma + valor # vamos exibir a soma dos valores do vetor print("A soma dos valores do vetor é: {0}".format(soma)) if __name__== "__main__": main() |
Mais Desafios de Programação e Exercícios e Algoritmos Resolvidos de Python |
Veja mais Dicas e truques de Python |
Dicas e truques de outras linguagens |
Códigos Fonte |
Software de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais |
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais |
Linguagens Mais Populares |
1º lugar: Java |