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.
Bubble Sort: a cada passo do algoritmo elementos adjacentes do vetor são comparados e, se estiverem fora de ordem, suas posições são trocadas. Ao final do primeiro passo o elemento de maior valor é posicionado corretamente, ao final do segundo passo o segundo maior valor e assim sucessivamente. Para ressaltar as trocas, ilustramos o comportamento do algoritmo a seguir para uma lista com os elementos dispostos inicialmente em ordem decrescente. O seu programa irá imprimir apenas o quadro final de cada passo, mas, para fins didáticos, as trocas intermediárias também foram exibidas.
| trocas intermediárias | quadro final |
|
|---|---|---|
| Passo 0 (entrada) |
| |
| Passo 1 | |
|
| Passo 2 | |
|
| Passo 3 | |
|
| Passo 4 | |
Selection Sort: no primeiro passo do algoritmo, o elemento que
estiver ocupando a posição 0 da lista irá ser trocado com o elemento de
menor valor. No segundo passo, o elemento da posição 1
irá trocar de lugar com o segundo menor elemento e assim
sucessivamente. Como apenas uma troca é necessária por passo,
ilustraremos apenas o quadro final considerando como entrada a
lista [4, 5, 2, 3, 1].
| quadro final |
|
|---|---|
| Passo 0 (entrada) |
|
| Passo 1 | |
| Passo 2 | |
| Passo 3 | |
| Passo 4 | |
Insertion Sort: a cada passo i do
algoritmo, o elemento da posição i é inserido na
sublista ordenada que vai do elemento 0 ao
elemento i-1. Nos diagramas a seguir, para
facilitar a visualização, simularemos uma remoção do elemento da
posição i e apresentaremos os deslocamentos sem
mostrar valores duplicados. O quadro final irá apresentar a
inserção do valor na posição adequada. Novamente, para ressaltar
os deslocamentos utilizaremos como entrada uma lista com os
elementos posicionados em ordem decrescente.
| elemento da posição i |
deslocamentos | quadro final |
|
|---|---|---|---|
| Passo 0 (entrada) |
| ||
| Passo 1 | |
|
|
| Passo 2 | |
|
|
| Passo 3 | |
|
|
| Passo 4 | |
|
|
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
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.
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.
Uma troca em Python pode ser escrita em apenas uma linha de código como duas atribuições simultâneas.
$ python3
>>> a = 3
>>> b = 5
>>> a, b = b, a
>>> print(a)
5
>>> print(b)
3
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.
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?
.................
. |.
. | |.
. | | |.
. | | ||.
. | ||||.
. ||||||.
. |||||||.
. ||||||||.
. |||||||||.
. ||||||||||.
. |||||||||||.
. ||||||||||||.
. |||||||||||||.
. ||||||||||||||.
.|||||||||||||||.
.................