Nesta tarefa, analisaremos detalhadamente as trocas executadas pelo
algoritmo de ordenação Bubble 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.
..............
. | .
. | | .
. | | | .
. | | || .
. | | ||| .
. | || ||| .
. | || ||| |.
. | || |||||.
. |||| |||||.
.| |||| |||||.
.| ||||||||||.
.||||||||||||.
..............A ideia básica do Bubble Sort baseia-se em comparar
elementos adjacentes da lista e, se estiverem fora de ordem,
trocá-los. Ao final da primeira passada na lista, o elemento de
maior valor estará posicionado corretamente na última
posição, ao final da segunda passada o segundo maior
valor na penúltima posição e assim
sucessivamente. Abaixo, ilustramos o comportamento do algoritmo com
a lista [4, 3, 2, 1].
......
.| .
.|| .
.||| .
.||||.
......
......
. | .
.|| .
.||| .
.||||.
......
......
. | .
.| | .
.||| .
.||||.
......
......
. |.
.| |.
.|| |.
.||||.
......
......
. |.
. | |.
.|| |.
.||||.
......
......
. |.
. ||.
.| ||.
.||||.
......
......
. |.
. ||.
. |||.
.||||.
......O algoritmo Bubble Sort é simples de entender, mas não é muito eficiente... Para mais informações sobre algoritmos de ordenação em Python consulte runstone.academy --- sorting.
A entrada conterá uma única linha com uma lista de inteiros com valores entre 1 e 9.
A saída conterá um quadro com o estado inicial da lista e um quadro ilustrando cada uma das trocas executadas pelo algoritmo. O último quadro deve conter a lista ordenada. Se a lista já estiver ordenada na entrada, apenas o quadro inicial deverá ser mostrado. Em caso de dúvidas, consulte os arquivos com as respostas dos testes.
Esta tarefa contém 7 testes abertos e 3 testes fechados. Veja na tabela abaixo os quatro primeiros testes e seus respectivos resultados. Consulte os outros testes e resultados no link Testes para a tarefa 12 de mc102 ou no arquivo aux12.zip
| arq01.in | arq02.in | arq03.in | arq04.in |
|---|---|---|---|
|
|
|
|
|
|
|
|
| arq01.res | arq02.res | arq03.res | arq04.res |
Veja aqui a
página de submissão da tarefa. O arquivo a ser
submetido deve se chamar lab12.py. No
link Arquivos
auxiliares há um
arquivo aux12.zip que
contém todos os arquivos de testes abertos e seus respectivos
resultados compactados.
O limite máximo será de 30 submissões. Serão considerados os resultados da última submissão.
O peso desta tarefa é 2.
O prazo final para submissão é 12/07/2020.
A nota desta tarefa é proporcional ao número de testes que executaram corretamente, desde que o código esteja coerente com o enunciado. A submissão de um código que não implementa o algoritmo requisitado, 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.