Métodos de Ordenação

Motivação

• Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente.
• A ordenação visa facilitar a recuperação posterior de itens do conjunto ordenado.
• Ex: Lista telefônica, Agenda de contatos, etc.
• Métodos de ordenação típicos:
• Bubble Sort, Selection Sort, Insertion Sort, QuickSort, Merge Sort, dentre outros.

Parêntese necessário:

Troca de valores entre duas variáveis

Há duas maneiras básicas de fazer troca de valores entre duas variáveis em Python

• Específica à linguagem Python:
• Dadas duas variáveis existentes a e b, basta fazer:

a, b = b, a

• Comum a todas as linguagens imperativas:
• Dadas duas variáveis existentes a e b, é preciso usar uma variável adicional auxiliar:

aux = a

a = b

b = aux

Neste documento, usaremos sempre a primeira forma. Mas, deve-se lembrar da segunda ao usar outra linguagem.

Bubble Sort ou Ordenação por Bolhas

• O algoritmo Bubble Sort consiste em:
• percorrer a lista a ser ordenada várias vezes, comparando cada elemento com o seguinte, permutando suas posições, se eles não estiverem na ordem pretendida.
• Assim, cada vez que a lista é percorrida, o maior (ou o menor) elemento ainda não ordenado é colocado na sua posição de ordenação definitiva.
• Naturalmente, a lista será percorrida até que não haja mais trocas a se fazer, quando então ela estará ordenada.
• É o mais simples dos métodos, por isso o mais conhecido.

Bubble Sort ou Ordenação por Bolhas

Dada a lista:

lista = [5, 1, 9, 3, 7, 2]

tamanho = len(lista)

bolhaSubindo = True

i = tamanho

while bolhaSubindo:

bolhaSubindo = False

i = i - 1

for j in range(0, i):

if lista[j] > lista[j+1]:

lista[j],lista[j+1] = lista[j+1],lista[j]

bolhaSubindo = True

Bubble Sort ou Ordenação por Bolhas

​

# Outra forma de fazer a ordenação por bolhas

​

tamanho = len(lista)

for i in range(1, tamanho):

for j in range(tamanho-1, i-1, -1):

if (lista[j-1] > lista[j]):

lista[j],lista[j-1] = lista[j-1],lista[j]

​

Dada a lista lista = [5, 1, 9, 3, 7, 2], rastreie a execução do código (faça o teste de mesa) para ver o que ocorre com a lista em cada passo da execução do programa de ordenação.

Selection Sort ou Ordenação por Seleção

• Um dos algoritmos mais simples de ordenação;
• Algoritmo:
• Selecione o menor item do vetor.
• Troque-o com o item da primeira posição do vetor.
• Repita essas duas operações com os n - 1 itens restantes, depois com os n - 2 itens, até que reste apenas um elemento.

Selection Sort ou Ordenação por Seleção

tamanho = len(lista)

for i in range(0, tamanho-1):

min = i

for j in range(i+1, tamanho):

# Encontra o menor

if lista[j] < lista[min]:

min = j

lista[i], lista[min] = lista[min], lista[i]

Selection Sort ou Ordenação por Seleção

{5, 1, 9, 3, 7, 2}

{1, 5, 9, 3, 7, 2}

{1, 2, 9, 3, 7, 5}

...........

........

​

Finalizar os valores da lista, junto com o teste de mesa

Dada a lista lista = [5, 1, 9, 3, 7, 2]

Insertion Sort ou Ordenação por Inserção

• É o terceiro dos algoritmos mais simples;
• Algoritmo:
• Ordena os dois primeiros membros do arranjo;
• Em seguida, insere o terceiro membro na sua posição ordenada com relação aos dois primeiros membros. Então, insere o quarto elemento na lista dos três, e assim por diante, até que todos os elementos tenham sido inseridos.

Insertion Sort ou Ordenação por Inserção

Insertion Sort ou Ordenação por Inserção

tamanho = len(lista)

for i in range(1, tamanho):

aux = lista[i]

j = i - 1

while j >= 0 and aux < lista[j]:

lista[j+1] = lista[j]

j -= 1

lista[j+1] = aux

{5, 1, 9, 3, 7, 2}

{1, 5, 9, 3, 7, 2}

{1, 3, 5, 9, 7, 2}

...........

........

​

Finalizar os valores da lista, junto com o teste de mesa

Dada a lista lista = [5, 1, 9, 3, 7, 2]

Funções de ordenação em Python

Há duas funções úteis de ordenação em Python:

• Aplique o método .sort() a uma lista e a ordene:

x = [5, 1, 9, 3, 7, 2]

x.sort()

print(x)

• Aplique a função sorted(coleção) a uma coleção (lista, tupla ou dicionário) e gere uma lista com os mesmos dados da coleção original, mas ordenada:

x = [5, 1, 9, 3, 7, 2]

y = sorted(x)

print(y)

print(x)

print(sorted((5,1,9,3,7,2)))

print(sorted({5:10,1:12,9:14,3:16,7:18,2:20}))