Aula 17: Ordenação de listas

Tópicos

Aulas a distância - Google Meet:

Para verem os vídeos, vocês devem estar logados no e-mail da usp.

Problema 1:

Dada uma lista com 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] = tmp
A 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 imax
No 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]

Problema 2:

Dadas 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