CS50-MCZ

Sort

Problema a Resolver

Neste problema, você analisará três programas de classificação (compilados!) para determinar quais algoritmos eles usam. Em um arquivo chamado answers.txt em uma pasta chamada sort, registre suas respostas, junto com uma explicação de cada programa, preenchendo os espaços marcados como TODO.

Começando

Passo a Passo

Eis aqui um passo a passo para a resolução do problema.

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

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 wget https://cdn.cs50.net/2023/fall/psets/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 (em inglês), 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/problems/2024/x/sort

Como enviar

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

submit50 cs50/problems/2024/x/sort