n > 0
números inteiros,
faça uma função para ordenar os seus elementos em ordem crescente.
Solução 1:
Utilizaremos a seguinte função auxiliar
para realizar a troca entre os elementos da lista L
nos índices i
e j
:
def troca(L, i, j): tmp = L[i] #Guarda cópia de backup do valor L[i] em tmp. L[i] = L[j] L[j] = tmpA primeira solução apresentada utiliza a função auxiliar abaixo que devolve o índice do maior elemento da lista compreendido entre os índices de
0
a n-1
.
def indice_maior(L, n): imax = 0 for i in range(1,n): if L[i] > L[imax]: imax = i return imaxNo algoritmo abaixo, a cada passo o maior elemento da lista de
n
elementos
é encontrado, e colocado na sua posição final definitiva
de índice n-1
no final da lista.
O processo se repete para o trecho da lista remanescente,
composto pelos primeiros n-1
elementos ainda não ordenados
(do índice zero até n-2
),
e assim por diante para subtrechos cada vez menores, até ter toda a lista ordenada.
Este algoritmo é conhecido como algoritmo de ordenação
por seleção simples.
def ordenacao_selecao(L): """Ordenação por seleção: A cada passo o maior elemento da lista é encontrado e colocado na sua posição final definitiva. O processo se repete para o trecho da lista remanescente.""" n = len(L) for tam in range(n, 1, -1): imax = indice_maior(L, tam) troca(L, imax, tam-1)No código acima, o laço controla em
tam
o tamanho da porção
da lista a ser ordenada (elementos de
L[0]
até L[tam-1]
).
A chamada da função indice_maior
busca e armazena em imax
o índice do maior elemento
presente no subtrecho do vetor a ser ordenado.
O elemento L[imax]
é então
movido para a última posição
do subtrecho (L[tam-1]
),
ocupando assim a sua posição definitiva.
Inicialmente, o subtrecho a ser ordenado
corresponde a toda a lista (elementos de
L[0]
até L[n-1]
).
A medida que os maiores valores são movidos
para o final da lista, temos a correspondente redução
do subtrecho remanescente a ser ordenado.
Solução 2:
O próximo algoritmo é conhecido como
bubble sort.
O laço mais interno percorre a lista
em j
comparando elementos consecutivos da lista (L[j]
e
L[j+1]
) e trocando a sua ordem sempre que
eles estiverem fora de ordem, isto é L[j] > L[j+1]
.
Após a primeira varredura, o maior elemento da lista
vai ocupar a última posição da lista,
ou seja sua posição final definitiva na lista ordenada.
A medida que os maiores valores são movidos
para o final da lista, temos a correspondente redução
do subtrecho remanescente a ser ordenado, até que
toda a lista esteja ordenada.
def ordenacao_bolha(L): 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)Uma segunda versão do algoritmo bubble sort é apresentada abaixo. Essa variante possui um segundo critério de parada do laço. Sempre que a lista é percorrida no laço mais interno, sem que haja trocas de elementos, podemos concluir que a lista já se encontra ordenada e podemos interromper o processo.
def ordenacao_bolha(L): n = len(L) for i in range(n-1,0,-1): houvetroca = False for j in range(0,i): if L[j] > L[j+1]: troca(L, j, j+1) houvetroca = True if not houvetroca: break
Solução 3:
Ordenação por inserção: Assume que uma parte da sequência já está ordenada, e insere mais um elemento no lugar apropriado.
def ordenacao_insercao(L): n = len(L) for i in range(0,n-1): # Insere L[i+1] em L[0],...,L[i]. x = L[i+1] j = i while j >= 0 and L[j] > x: L[j+1] = L[j] j -= 1 L[j+1] = x
Solução 4:
Podemos simplesmente usar o método sort()
da classe list
disponível no Python.
>>> L = [8,3,7,1,2]
>>> L.sort()
>>> print(L)
[1, 2, 3, 7, 8]
n > 0
observações
x1
, x2
, ..., xn
, em uma lista com n
elementos
da classe float, faça uma função para
calcular a sua mediana.
Mediana é o valor que separa a metade maior e a metade menor das
observações.
Por exemplo, no conjunto de dados {1, 3, 3, 5, 7, 8, 9}
,
a mediana é 5.
Se houver um número par de observações,
não há um único valor do meio.
Então, a mediana é definida como a média
dos dois valores do meio. Por exemplo,
no conjunto de dados {3, 5, 7, 9}
, a mediana
é (5+7)/2=6
.
Solução 1:
Ordenamos uma cópia da lista para encontrar o elemento central, sem alterar a lista original fornecida.
def mediana(L): C = L[:] C.sort() if len(L)%2 != 0: m = len(L)//2 return C[m] else: m = len(L)//2 return (C[m-1]+C[m])/2.0
Solução 2:
Podemos simplesmente usar a função statistics.median()
do módulo statistics
.
>>> import statistics
>>> statistics.median([1,2])
1.5
>>> statistics.median([1,8,2])
2