Você está aqui: Python ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca)

Como implementar a ordenação Quicksort em Python - Apostila de Python para iniciantes

Quantidade 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 Python

Quantidade 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 valores

Quantidade 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]
Escreva um programa Python console ou GUI que usa um laço for para percorrer todos os elementos deste vetor e exibir a soma de seus valores. Seu programa deverá exibir uma saída com a mensagem:

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

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware 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 funcionalidadesControle 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
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 54 usuários muito felizes estudando em nosso site.