Algoritmos de Ordenação (Python)

Prof. Rodrigo Rocha <rodrigorgs@ufba.br>

Motivação

Ordenação: o quê e por quê

• Dada uma lista de itens, a ordenação (também chamado de classificação) consiste em mudar a ordem dos itens de acordo com determinado critério (ex.: ordem numérica crescente, ordem alfabética…)
• Muitos exemplos na vida real:
• Dicionário da língua portuguesa (ordem alfabética)
• Classificação de candidatos em um concurso (ordem decrescente de nota)
• Buscar algo em uma lista é muito mais rápido se ela estiver ordenada

Ordenação: definição

Entrada:

lista v, com n elementos

Saída:

lista v, na qual as posições dos elementos foram trocadas de forma que

v[0] ≤ v[1] ≤ v[2] ≤ … ≤ v[n-1]

​

Conceitos básicos

Algoritmo de ordenação

Existem diversos algoritmos de ordenação.

Muitos algoritmos de ordenação se baseiam em duas operações:

• Comparar dois elementos da lista
• Permutar dois elementos da lista (trocar um de lugar com o outro)

​

​

Código para permutar dois elementos

Nem todas as linguagens de programação possuem essa forma compacta de permutar dois elementos; por isso, é importante conhecer a outra forma.

Dada uma lista v e dois índices, i e j, para permutar v[i] e v[j]:

temp = v[i]

v[i] = v[j]

v[j] = temp

�

Outra forma, mais compacta:

v[i], v[j] = v[j], v[i]

Algoritmo de ordenação: experimente você

Experimente ordenar uma lista de cartas usando apenas comparação e permutação de cartas, duas a duas:

​

​

​

https://pt.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/sorting

Algoritmo de ordenação: desempenho

Alguns algoritmos tendem a ser mais rápidos do que outros.

https://www.youtube.com/watch?v=cVMKXKoGu_Y

Ordenação incremental

Os algoritmos que estudaremos são incrementais:

• A lista é (conceitualmente) dividida em duas partes: a parte que já está ordenada e a parte que ainda não está ordenada
• A cada iteração do algoritmo, a parte ordenada se expande
• Ao final do algoritmo, a parte ordenada representa 100% da lista

Ordenação incremental

Aqui está um programa que imprime a lista toda, depois todos os elementos exceto o último, depois exceto os dois últimos, exceto os três últimos etc. Ele será base para alguns algoritmos de ordenação que veremos a seguir.

​

v = [1, 2, 3, 4, 5, 6]

n = len(v)

for fim in range(n - 1, 0, -1): # fim = n-1, n-2, …, 1

print(v[0:fim+1]) # imprime de 0 até fim

1ª

2ª

3ª

4ª

5ª

iteração

Ordenação por seleção

(Selection sort)

Ordenação por seleção: ideia geral

A cada iteração, seleciona o maior elemento e move para o final

​

Ordenação por seleção: intuição

Inicialmente, toda a lista está não-ordenada

1. Seleciona o maior elemento da lista não-ordenada
2. Permuta o maior elemento com o último
3. O último elemento da lista não-ordenada agora faz parte da lista ordenada
4. Repete

Ordenação por seleção

Vamos usar 3 variáveis:

• n: tamanho da lista v
• fim: índice do último elemento da parte não-ordenada da lista
• imaior: índice do maior elemento da parte não-ordenada da lista

n = len(v)

for fim in range(n - 1, 0, -1): # n-1, n-2, …, 1

# Determina o índice do maior elemento (imaior) de v[0] a v[fim]

# ...� # Permuta o maior elemento (v[imaior]) com o último (v[fim])

# ...

Ordenação por seleção

n-1, n-2, …, 1

1, 2, …, fim

n = len(v)

for fim in range(n - 1, 0, -1):

# Determina o índice do maior elemento (imaior)

imaior = 0

for i in range(1, fim + 1):

if v[i] > v[imaior]:

imaior = i

# Permuta o maior com o último

v[imaior], v[fim] = v[fim], v[imaior]

Visualize aqui: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/SelectionSort.html

Ordenação bolha

(Bubble sort)

Ordenação bolha: ideia geral

Para cada elemento, se ele for maior do que o próximo, troca

​

Ordenação bolha: intuição

Inicialmente, toda a lista está não-ordenada

• Percorre a lista não-ordenada, da esquerda para a direita, comparando cada elemento com o próximo; se eles estiverem fora de ordem, permuta
• O maior elemento de todos acaba indo para a última posição; por isso, o último elemento da lista não-ordenada agora faz parte da lista ordenada
• Repete

Ordenação bolha

Ao final do loop mais interno, o maior elemento estará na posição fim

O início é igual à ordenação por seleção

Visualize aqui: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/BubbleSort.html

n = len(v)

for fim in range(n - 1, 0, -1):

for i in range(0, fim):

if v[i] > v[i+1]:

v[i], v[i+1] = v[i+1], v[i]

Desempenho

Ordenação bolha em geral possui desempenho ruim:

https://youtu.be/9zqQpRRX6oU

Ordenação por inserção

(Insertion sort)

Ordenação por inserção: ideia geral

Para cada elemento, insira-o na sua posição correta�dentre os elementos que vêm antes dele

(é o algoritmo geralmente usado por�jogadores de jogos de cartas)

Ordenação por inserção: intuição

Aqui, vamos inverter a lógica: a parte ordenada da lista fica no início e a não-ordenada, no final

Inicialmente, consideramos que do segundo elemento em diante ainda não está ordenado

• Seleciona o primeiro elemento da lista não-ordenada e compara com o anterior; se estiverem fora de ordem, permuta
1. Repete a comparação até o elemento chegar à sua posição correta dentro da lista ordenada
• A lista ordenada agora possui um elemento a mais
• Repete

Ordenação por inserção

Algumas entradas para testar:

1 2 3�1 3 2�2 1 3�2 3 1�3 1 2�3 2 1

Este código está quase certo, mas possui um erro sutil.

Você consegue pensar em uma entrada que gera um erro no interpretador Python?

n = len(v)

for inicio in range(1, n):

i = inicio

while v[i] < v[i-1]:

v[i], v[i-1] = v[i-1], v[i]

i -= 1

Ordenação por inserção

Se o elemento chegou à posição 0, ele já está no lugar correto.

Nesse caso, não podemos compará-lo com o elemento anterior (pois ele é o primeiro!)

Ou seja, vamos percorrendo a lista até chegar à posição 1; depois disso, paramos

​

n = len(v)

for inicio in range(1, n):

i = inicio

while i >= 1 and v[i] < v[i-1]:

v[i], v[i-1] = v[i-1], v[i]

i -= 1

Visualize aqui: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/InsertionSort.html

Outros algoritmos de ordenação

Variações nos algoritmos

• Os algoritmos que vimos podem ser implementados de diferentes maneiras
• Ex.: no selection sort, no lugar de mover o maior elemento para o fim, podemos mover o menor elemento para o início

Outros algoritmos de ordenação

Outros algoritmos não serão explorados nesta disciplina, mas segue uma pequena lista de algoritmos para o estudante curioso:

• merge sort
• quicksort (em geral muito eficiente)
• timsort (algoritmo usado pela função sorted do Python)
• radix sort (não é baseado em comparações)

Problemas

Ordem alfabética decrescente

Dada uma lista de palavras separadas por espaço (sem acentos, apenas letras minúsculas), imprima as palavras em ordem alfabética decrescente, separadas por espaço.

​

​

Ordem alfabética decrescente

Aqui, usamos ordenação por inserção, mas poderíamos ter usado qualquer algoritmo.

A única mudança no algoritmo original é que, agora, permutamos quando o elemento é maior que o anterior.

Ou seja, os elementos maiores vão para o início da lista.

v = input().split()

n = len(v)

for inicio in range(1, n):

i = inicio

while i >= 1 and v[i] > v[i-1]:

v[i], v[i-1] = v[i-1], v[i]

i -= 1

print(" ".join(v))

​

Ordenação por múltiplos critérios

Dada uma lista de nomes de alunos e suas notas, imprima os alunos em ordem decrescente de nota, juntamente com sua nota. Em caso de empate, comece pelo nome que vem primeiro na ordem alfabética.

Entrada: um número N, indicando a quantidade de alunos, seguido de N linhas, cada uma consistindo do primeiro nome de um aluno, um espaço e sua nota. Exemplo: 4 sicrano 8.2 fulano 9.5 beltrana 9.5 zutana 8.8

​

Ordenação por múltiplos critérios

# Entrada

n = int(input())

v = []

for i in range(n):

nome, nota = input().split()

v.append({"nome": nome,

"nota": float(nota)})

# Ordenação

for inicio in range(1, n):

i = inicio

while i >= 1 and \

(v[i]["nota"] > v[i-1]["nota"] or

(v[i]["nota"] == v[i-1]["nota"] and

v[i]["nome"] < v[i-1]["nome"])):

v[i], v[i-1] = v[i-1], v[i]

i -= 1

​

# Saída

for aluno in v:

print(aluno["nome"], aluno["nota"])

​

​