Escreva uma função que, dada uma lista com n > 0 números inteiros, ordene os seus elementos em ordem crescente.
def troca(L, i, j):
""" (list, int, int) -> None
Troca os valores dos elementos nas posições
i e j da lista L
"""
tmp = L[i]
L[i] = L[j]
L[j] = tmp
def indice_maior(L, fim):
""" (list, n) -> int
Devolve a posição do maior elemento da lista L
encontrado entre as posições 0 e fim da lista.
"""
imax = 0
for i in range(1,fim+1):
if L[i] > L[imax]:
imax = i
return imax
def ordenacao_selecao(L):
""" (list) -> None
Recebe uma lista L e ordena os elementos de L
em ordem crescente de valor.
Usa o algoritmo da Ordenação por Seleção:
A cada passo o maior elemento de L é
encontrado e colocado na sua posição
final definitiva. O processo se repete para o
trecho da lista remanescente.
"""
for fim in range(len(L)-1, 0, -1):
imax = indice_maior(L, fim)
troca(L, imax, fim)
################
# Testa a função de ordenação
lista = [40,20,50,10,30,20]
print("A lista", lista, "ordenada fica:", end="")
ordenacao_selecao(lista)
print(lista)
def troca(L, i, j):
""" (list, int, int) -> None
Troca os valores dos elementos nas posições
i e j da lista L
"""
tmp = L[i]
L[i] = L[j]
L[j] = tmp
def ordenacao_bolha(L):
'''
(list) -> None
Recebe uma lista L e ordena os elementos de L
em ordem crescente de valor.
Usa o algoritmo da Ordenação por Bolha:
Este algoritmo percorre a lista do início ao fim,
verificando a ordem dos elementos dois a dois,
e trocando-os de lugar se necessário.
Cada execução do laço mais externo coloca em seu
lugar correto um número da lista.
'''
n = len(L)
for i in range(n-1, 0, -1):
for j in range(0,i):
if L[j] > L[j+1]:
troca(L, j, j+1)
################
# Testa a função de ordenação
lista = [40,20,50,10,30,20]
print("A lista", lista, "ordenada fica:", end="")
ordenacao_bolha(lista)
print(lista)
def ordenacao_insercao(L):
'''
(list) -> None
Recebe uma lista L e ordena os elementos de L
em ordem crescente de valor.
Usa o algoritmo da Ordenação por Inserção:
Ele percorre cada posição i da lista, começando com o índice 1.
Para uma dada posição i, o algoritmo insere o valor da posição i
na sublista L[1..i] de modo a mantê-la ordenada.
'''
n = len(L)
for i in range(1,n):
# Insere L[i] em L[0],...,L[i-1].
x = L[i]
j = i-1
while j >= 0 and L[j] > x:
L[j+1] = L[j]
j -= 1
L[j+1] = x
################
# Testa a função de ordenação
lista = [40,20,50,10,30,20]
print("A lista", lista, "ordenada fica:", end="")
ordenacao_insercao(lista)
print(lista)
Faça um programa em Python que leia uma planilha no formato CSV (comma-separated values), onde o caracter separador de campos é o ponto-e-vírgula (";"), em uma matriz (lista de listas) e que gere um novo arquivo no formato CSV contendo a planilha ordenada pelo seu primeiro campo. Todas as linhas do arquivo a ser lido contêm o mesmo número de campos.
Por exemplo, uma entrada válida para o seu programa poderia ser o arquivo "notas.csv", cujo conteúdo é mostrado abaixo:
Olavo Bilac;8.3;3.1;4.9;6.9
Ferreira Gullar;5.6;4.2;7.8;9
Cora Coralina;9.5;8.4;9.2;7.7
Vinicius de Moraes;3.8;6.5;4.2;2.6
Adelia Prado;6.3;7.1;5.5;9.4
Carlos Drummond de Andrade;10;9.6;10;8.9
Manuel Bandeira;2.5;6.7;3.6;4
Cecilia Meireles;8.7;10;7.4;9.5
O conteúdo do arquivo gerado pelo programa para o arquivo acima deve ser análogo ao do arquivo "notas_ordenadas.csv", cujo conteúdo é mostrado abaixo:
Adelia Prado;6.3;7.1;5.5;9.4
Carlos Drummond de Andrade;10;9.6;10;8.9
Cecilia Meireles;8.7;10;7.4;9.5
Cora Coralina;9.5;8.4;9.2;7.7
Ferreira Gullar;5.6;4.2;7.8;9
Manuel Bandeira;2.5;6.7;3.6;4
Olavo Bilac;8.3;3.1;4.9;6.9
Vinicius de Moraes;3.8;6.5;4.2;2.6
def ordena(matriz):
''' (list -> None)
Função que recebe uma matriz (lista de listas) e ordena as linhas
dessa matriz em ordem crescente de valor da coluna 0.
A função implementa o algoritmo de Ordenação por Seleção.
'''
ultima_posicao = len(matriz)-1
# laço que começa na posição da última linha da matriz e vai até a posição da penúltima linha
for fim_atual in range(ultima_posicao,0,-1):
# Encontra entre as posições 0 e fim_atual a linha da matriz que possui o maior valor para a coluna 0
imax = 0
for i in range(1,fim_atual+1):
if matriz[i][0] > matriz[imax][0]:
imax = i
# Troca as linhas matriz[imax] e matriz[fim_atual],
# para colocar a linha com maior valor para a coluna 0 na posição fim_atual
# (que é o lugar correto dessa linha na matriz ordenada)
tmp = matriz[fim_atual]
matriz[fim_atual] = matriz[imax]
matriz[imax] = tmp
def main():
# Leitura do arquivo de entrada
nome_arquivo = input("Digite o nome do arquivo CSV a ser lido: ")
arquivo = open(nome_arquivo, 'r')
matriz = []
for linha in arquivo:
l = linha.strip() # remove caracteres "brancos" do início e do final da linha lida
if len(l) > 0:
palavras = l.split(";") # cria uma lista com os valores na linha que estão separados por ";"
matriz.append(palavras) # adiciona uma nova linha na matriz;
# essa linha é a lista de valores extraídos da última linha lida do arquivo
arquivo.close()
ordena(matriz)
# Gravação do arquivo de saída
nome_arquivo = input("Digite o nome do arquivo CSV ordenado a ser gravado: ")
arquivo = open(nome_arquivo, 'w')
n = len(matriz)
m = len(matriz[0])
for i in range(n): # laço que grava uma linha da matriz no arquivo
for j in range(m-1): # laço que grava no arquivo todos os valores de uma linha da matriz menos o último valor
arquivo.write(matriz[i][j])
arquivo.write(";")
arquivo.write(matriz[i][m-1]) # grava no arquivo o último valor da linha;
# esse valor é gravado separadamente porque ele não deve vir seguido de ";"
# mas sim deve vir seguido de um caractere de quebra de linha "\n"
arquivo.write("\n")
arquivo.close()
main()
As paginas a seguir "ilustram" o funcionamento dos três algoritmos de ordenação implementados acima por meio de danças folclóricas :))
Uma explicacao mais teórica pode ser vista em: http://www.ime.usp.br/~pf/algoritmos/aulas/ordena.html