Lab 3: Sort

Analyze three sorting programs to determine which algorithms they use.

Background

Recall from lecture that we saw a few algorithms for sorting a sequence of numbers: selection sort, bubble sort, and merge sort.

• Selection sort iterates through the unsorted portions of a list, selecting the smallest element each time and moving it to its correct location.
• Bubble sort compares pairs of adjacent values one at a time and swaps them if they are in the incorrect order. This continues until the list is sorted.
• Merge sort recursively divides the list into two repeatedly and then merges the smaller lists back into a larger one in the correct order.

Accepting this Lab

1. Accept this lab via GitHub Classroom.
2. After about a minute, refresh the page and ensure you see “You’re ready to go!”.

Getting Started

Log into code.cs50.io, click on your terminal window, and execute cd by itself. You should find that your terminal window’s prompt resembles the below:

$

Next execute

get50 sort

in order to download a directory called sort into your codespace.

Then execute

cd sort

in order to change into that directory. Your prompt should now resemble the below:

sort/ $

Execute ls by itself, and you should see a collection of .txt files alongside executable programs sort1, sort2, and sort3.

If you run into any trouble, follow these same steps steps again and see if you can determine where you went wrong!

Instructions

Provided to you are three already-compiled C programs, sort1, sort2, and sort3. Each of these programs implements a different sorting algorithm: selection sort, bubble sort, or merge sort (though not necessarily in that order!). Your task is to determine which sorting algorithm is used by each file.

• sort1, sort2, and sort3 are binary files, so you won’t be able to view the C source code for each. To assess which sort implements which algorithm, run the sorts on different lists of values.
• Multiple .txt files are provided to you. These files contain n lines of values, either reversed, shuffled, or sorted.
  • For example, reversed10000.txt contains 10000 lines of numbers that are reversed from 10000, while random100000.txt contains 100000 lines of numbers that are in random order.
• To run the sorts on the text files, in the terminal, run ./[program_name] [text_file.txt]. Make sure you have made use of cd to move into the sort directory!
  • For example, to sort reversed10000.txt with sort1, run ./sort1 reversed10000.txt.
• You may find it helpful to time your sorts. To do so, run time ./[sort_file] [text_file.txt].
  • For example, you could run time ./sort1 reversed10000.txt to run sort1 on 10,000 reversed numbers. At the end of your terminal’s output, you can look at the real time to see how much time actually elapsed while running the program.
• Record your answers in answers.txt, along with an explanation for each program, by filling in the blanks marked TODO.

Walkthrough

Hints

• The different types of .txt files may help you determine which sort is which. Consider how each algorithm performs with an already sorted list. How about a reversed list? Or shuffled list? It may help to work through a smaller list of each type and walk through each sorting process.

How to Check Your Answers

Execute the below to evaluate the correctness of your answers using check50. But be sure to fill in your explanations as well, which check50 won’t check here!

check50 cs50/labs/2021/fall/sort

How to Submit

In your terminal, execute the below to submit your work.

submit50 sort

You may submit as many times as you would like up until the deadline. To confirm your submission, go to github.com/classroom50/sort-USERNAME where USERNAME is your GitHub username. You should see the code from your latest submission.

Labs are assessed only on whether you’ve submitted an honest attempt.

sort1 uses: Bubble Sort

How do you know?: On a large random file, sort1 takes much longer than an already-sorted file of the same size. For already-sorted files, sort1 returns results almost instantaneously, regardless of size. This suggests that sort1 has a different upper bound runtime than lower bound runtime. This is consistent with Bubble Sort, which runs in O(n^2) and Ω(n).

sort2 uses: Merge Sort

How do you know?: On larger random files, sort2 is the fastest of the three sorts. Since we know that Merge Sort runs in O(n log n) while Bubble Sort and Selection Sort run in the slower O(n^2), sort2 is likely Merge Sort.

sort3 uses: Selection Sort

How do you know?: On a large random file, sort3 takes just as long as sort1, but performs no better when the list is already sorted. This suggests that the algorithm runs in O(n^2) and Ω(n^2), which is consistent with Selection Sort.