MC102 - Algoritmos e Programação de Computadores

Algoritmos de ordenação

Nesta tarefa, aproveitaremos nossa experiência com ASC Art para analisarmos detalhadamente o funcionamento dos algoritmos de ordenação Bubble Sort, Selection Sort e Insertion Sort. Para nosso estudo, utilizaremos um visualizador para listas de inteiros contruído a partir de barras feitas com caracteres | de altura proporcional ao valor dos inteiros representados. Veja, como exemplo, o visualizador para uma lista com os inteiros [3, 1, 12, 4, 10, 7, 2, 11, 9, 8, 5, 6], adornado com uma moldura feita com pontos.

..............
.  |         .
.  |    |    .
.  | |  |    .
.  | |  ||   .
.  | |  |||  .
.  | || |||  .
.  | || ||| |.
.  | || |||||.
.  |||| |||||.
.| |||| |||||.
.| ||||||||||.
.||||||||||||.
..............

Para cada um dos algoritmos, para uma entrada com n inteiros, podemos definir n-1 passos. Estes algoritmos foram vistos em sala de aula e, portanto, apenas as características principais serão resumidas neste enunciado. Para mais informações, veja aqui uma ótima referência para este tema em Python.

Entrada

A entrada será o nome do algoritmo (bubble, selection ou insertion) e uma lista de inteiros com valores entre 1 e 15.

bubble
5 1 2 3 4    

Saída

A saída conterá o estado inicial da lista (passo 0) e os quadros representando os passos dos algoritmos conforme descrição acima. A exibição dos passos deverá ser interrompida quando a saída já estiver ordenada, mesmo que nem todos os passos tenham sido mostrados. Ou seja, no caso de lista inicialmente ordenada, apenas um quadro será exibido. Para o exemplo anterior, a saída terá apenas dois quadros.

.......
.|    .
.|   |.
.|  ||.
.| |||.
.|||||.
.......
.......
.    |.
.   ||.
.  |||.
. ||||.
.|||||.
.......

Note que, conforme a entrada, é possível que não haja alteração na lista (e consequentemente do quadro) após a execução de um passo. Por exemplo, no Selection Sort, o elemento de menor valor em um passo pode estar na posição correta, ainda que a lista não esteja ordenada. Nestes casos, os quadros repetidos irão aparecer na saída.

Testes para o SuSy

Esta tarefa terá 12 testes abertos, sendo 4 para cada um dos algoritmos. Favor consultar os arquivos no SuSy para verificar os detalhes dos testes. Haverá também 3 testes fechados, sendo 1 para cada algoritmo.

Dica de Python 3 para esta tarefa:

Orientações para submissão

Veja aqui a página de submissão da tarefa. Lembre-se que o arquivo a ser submetido deve se chamar main.py. No link Arquivos auxiliares há um arquivo arqs-10.zip que contém todos os arquivos de testes abertos e seus respectivos resultados compactados. Os arquivos executa-testes.py e executa-testes-windows.py também estão neste pacote.

Observe o limite máximo de 20 submissões

A nota final é proporcional ao número de testes que executaram corretamente. A submissão de um código que não implementa os algoritmos solicitados, mas que exibe as saídas esperadas dos testes abertos a partir da comparação de trechos da entrada será considerada fraude e acarretará a atribuição de nota zero à média final da disciplina.

O peso desta tarefa é 2.

O prazo final para submissão é 30/06/2018.

Desafio

Considerando a lista de inteiros [13, 2, 3, 1, 9, 4, 12, 5, 7, 6, 10, 14, 11, 8, 15] e o quadro intermediário do processo de ordenação exibido abaixo você é capaz de identificar qual algoritmo foi utilizado?

.................
.              |.
.           |  |.
.         | |  |.
.         | | ||.
.         | ||||.
.         ||||||.
.        |||||||.
.       ||||||||.
.      |||||||||.
.     ||||||||||.
.    |||||||||||.
.   ||||||||||||.
.  |||||||||||||.
. ||||||||||||||.
.|||||||||||||||.
.................