CS50-MCZ

Lab 3: Sort

Analisar três programas de ordenação para determinar quais algoritmos eles usam.

Contexto

Lembre-se da aula em que vimos alguns algoritmos para ordenar uma sequência de números: selection sort, bubble sort e merge sort.

• O selection sort itera pelas porções não ordenadas de uma lista, selecionando o menor elemento cada vez e movendo-o para a posição correta.
• O bubble sort compara pares de valores adjacentes um de cada vez e os troca se estiverem na ordem incorreta. Isso continua até que a lista esteja ordenada.
• O merge sort divide recursivamente a lista em duas repetidamente e depois mescla as listas menores de volta em uma maior na ordem correta.

Começando

Abra o VS Code.

Comece clicando dentro da janela do terminal e, em seguida, execute cd por si só. Você deve encontrar que seu "prompt" se assemelha ao abaixo.

$

Clique dentro dessa janela de terminal e execute

wget https://cdn.cs50.net/2022/fall/labs/3/sort.zip

digite Enter para baixar um arquivo ZIP chamado sort.zip em seu espaço de códigos. Tenha cuidado para não ignorar o espaço entre wget e a URL seguinte, ou qualquer outro caractere!

Agora execute

unzip sort.zip

para criar uma pasta chamada sort. Você não precisa mais do arquivo ZIP, então pode executar

rm sort.zip      

e responda com "y" seguido de Enter no prompt para remover o arquivo ZIP que você baixou.

Agora digite

cd sort

seguido de Enter para entrar (ou seja, abrir) nesse diretório. Seu prompt agora deve se parecer com o abaixo.

sort/ $    

Se tudo foi bem sucedido, você deve executar

ls    

e você deve ver uma coleção de arquivos .txt ao lado dos programas executáveis sort1, sort2 e sort3.

Se você encontrar algum problema, siga os mesmos passos novamente e veja se consegue determinar onde errou!

Instruções

Foram fornecidos três programas C já compilados: sort1, sort2 e sort3. Cada um desses programas implementa um algoritmo de ordenação diferente: selection sort, bubble sort ou merge sort (embora não necessariamente nessa ordem!). Sua tarefa é determinar qual algoritmo de ordenação é usado por cada arquivo.

• sort1, sort2 e sort3 são arquivos binários, portanto você não poderá visualizar o código-fonte C de cada um. Para avaliar qual ordenação implementa qual algoritmo, execute as ordenações em diferentes listas de valores.
• Vários arquivos .txt são fornecidos. Esses arquivos contêm n linhas de valores, invertidos, embaralhados ou ordenados.
  • Por exemplo, reversed10000.txt contém 10000 linhas de números que estão invertidos a partir de 10000, enquanto random10000.txt contém 10000 linhas de números que estão em ordem aleatória.
• Para executar as ordenações nos arquivos de texto, no terminal, execute ./[program_name] [text_file.txt]. Certifique-se de ter usado o comando cd para entrar no diretório sort!
  • Por exemplo, para ordenar reversed10000.txt com sort1, execute ./sort1 reversed10000.txt.
• Você pode achar útil cronometrar suas classificações. Para fazer isso, execute time ./[sort_file] [text_file.txt].
  • Por exemplo, você poderia executar time ./sort1 reversed10000.txt para executar o sort1 em 10.000 números invertidos. No final da saída do seu terminal, você pode olhar o tempo real para ver quanto tempo realmente decorreu enquanto o programa estava sendo executado.
• Registre suas respostas em answers.txt, juntamente com uma explicação para cada programa, preenchendo as lacunas marcadas com TODO.

Dicas

• Os diferentes tipos de arquivos .txt podem ajudá-lo a determinar qual é qual. Considere como cada algoritmo se comporta com uma lista já ordenada. E com uma lista invertida? E com uma lista embaralhada? Pode ser útil trabalhar com uma lista menor de cada tipo e percorrer cada processo de ordenação.

Como verificar suas respostas

Execute o código abaixo para avaliar a correção de suas respostas usando o check50. Mas lembre-se de preencher também suas explicações, que o check50 não verificará aqui!

check50 cs50/labs/2023/x/sort

Como enviar

No seu terminal, execute o seguinte para enviar seu trabalho.

submit50 cs50/labs/2023/x/sort