Algoritmos Elementares de Ordenação

Objetivo

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

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 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.

Exercício 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.

Exercício 3 - Algoritmo de seleção

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

Algoritmo de Ordenação por seleção

  • 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.

Exercício 4 - Algoritmo da bolha

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

Algoritmo de ordenação: método da “bolha”

  • 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.

Algoritmo de seleção: método da “bolha” melhorado

  • 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.