Algoritmos elementares de ordenação

Objetivo

Ao final dessa aula você vai saber escrever algoritmos elementares de ordenação.

Tópicos

• Ordenação: algoritmos elementares;
• Selection Sort
• Insertion Sort
• Buble Sort

Links Interessantes

• Animação de algoritmos de ordenação de Nicholas André Pinho de Oliveira.
• Sorting Algorithms Animation por David R. Martin.

Algoritmos de Elementares de Ordenação:

A ordenação de elementos em uma lista ou vetor é uma atividade fundamental em vários problemas computacionais. De forma geral, o problema pode ser definido como:

Dado uma lista seq com N elementos, rearranjar os elementos de seq de tal modo que eles fiquem em ordem crescente, ou seja, de tal forma que seq[0] <= seq[1] <= ... <= seq[N-1].

Exercício 24.1

Escreva uma função crescente que recebe uma lista seq e retorna True caso seq esteja em ordem crescente, e False caso contrário. Copie essa função nos demais exercícios para testar os seus próprios algoritmos de ordenação.

def main(): seq1 = [2, 4, 5, 8, 9, 11, 17, 21] print(seq1) if crescente(seq1): print("eh crescente") else: print("nao eh crescente") def crescente(seq): ''' (list) -> bool retorna True se seq esta em ordem crescente e False caso contrario ''' print("Vixe! ainda nao escrevi a funcao") return False main()

(ex24.1_tentativa)

Run Save Load

Exercício 24.2 - Algoritmo de inserção

O algoritmo de inserção é usado, por exemplo, para ordenar um baralho de cartas. A ideia é a seguinte:

1. Assuma que a primeira posição da lista seq (1a carta do baralho) está ordenada;
2. novo = 2
3. sabemos que todos os elementos anteriores ao elemento novo estão ordenados
4. insira o elemento novo (seq[novo]) na posição adequada na sub lista seq[0:novo], e desloque os demais elementos, para obter a lista ordenada até o elemento novo.
5. incremente novo e repita a partir do passo 3 até o último elemento da lista

Para entender esse algoritmo assista a animação desse método com dança folclórica romena ou o vídeo Insertion Sort.

Escreva abaixo a função insercao que implementa esse algoritmo. Uma característica importante para a eficiência de um algoritmo de ordenação é a capacidade de utilizar a mesma lista de entrada, rearranjando os elementos ao invés de criar uma nova lista ordenada. Faça isso na sua função.

def main(): seq1 = [54, 2, 11, 4, 17, 7, 21, 1] print(seq1) insercao(seq1) print(seq1) if not crescente(seq1): print("nao ", end='') print("eh crescente") def insercao( seq ): ''' (list) -> list ordena a lista seq usando o algoritmo de insercao ''' # escreva a funcao main()

(ex24.2_algoritmo_insercao)

Run Save Load

Exercício 24.3 - Algoritmo de seleção

O algoritmo de seleção utiliza a seguinte estratégia para ordenar uma lista seq com N elementos:

• Repita com pos variando de 0 até N-1:

  • acha o índice k do menor elemento na sub lista seq[pos:]
  • troca o elemento seq[k] com seq[pos]
  • nesse instante temos que a sub lista seq[0:pos+1] está ordenada.

Para entender esse algoritmo assista a animação desse método com dança cigana ou o vídeo Selection Sort.

Escreva a função selecao que implementa esse algoritmo. Uma característica importante para a eficiência de um algoritmo de ordenação é a capacidade de utilizar a mesma lista de entrada, rearranjando os elementos ao invés de criar uma nova lista ordenada. Faça isso na sua função.

def main(): seq1 = [54, 2, 11, 4, 17, 7, 21, 1] print(seq1) selecao(seq1) print(seq1) if not crescente(seq1): print("nao ", end='') print("eh crescente") def selecao( seq ): ''' (list) -> list ordena a lista seq usando o algoritmo de selecao ''' # escreva a funcao main()

(ex24.3_algoritmo_selecao)

Run Save Load

Exercício 24.4 - Algoritmo da bolha

O algoritmo da bolha utiliza a seguinte estratégia para ordenar uma lista seq com N elementos:

• Repita N-1 vezes:

  • varra a lista com pos variando de 1 até N-1:

    • se seq[pos] for menor que o elemento anterior então:

      • troca o elemento em pos com o seu anterior

A ideia é que, a cada varrida, elementos “grandes” são arrastados para a direita e elementos “pequenos” são arrastados para a esquerda da lista. Repetindo-se essas trocas por um número suficiente de vezes, obtemos a lista ordenado. No entanto, em muitos casos, é possível que a lista fique ordenada após algumas poucas trocas. Nesse caso, é possível melhorar esse algoritmo para que pare assim que se descubra que ele se tornou ordenado.

• houve_troca = True

• enquanto houve_troca:

  • houve_troca = False

  • varra a lista com pos variando de 1 até N-1:

    • se seq[pos] for menor que o elemento anterior então:

      • troca o elemento em pos com o seu anterior
      • houve_troca = True

Para entender esse algoritmo assista a animação desse método com dança folclórica húngara ou o vídeo Bubble Sort.

Escreva a função bolha que implementa esse algoritmo. Uma característica importante para a eficiência de um algoritmo de ordenação é a capacidade de utilizar a mesma lista de entrada, rearranjando os elementos ao invés de criar uma nova lista ordenada. Faça isso na sua função.

def main(): seq1 = [54, 2, 11, 4, 17, 7, 21, 1] print(seq1) bolha(seq1) print(seq1) if not crescente(seq1): print("nao ", end='') print("eh crescente") def bolha( seq ): ''' (list) -> list ordena a lista seq usando o algoritmo de bolha ''' # escreva a funcao main()

(ex24.4_algoritmo_bolha)

Run Save Load