# Lab 3: Sort

Labs are practice problems completed in your section, assessed on completion only. You are encouraged to collaborate with classmates on this lab!

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

- Accept this lab via GitHub Classroom.
- 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.

- For example,
- 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`

.

- For example, to sort
- 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.

- For example, you could run
- 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.

## Not sure how to solve?

### 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

- Download your
`answers.txt`

file by control-clicking or right-clicking on the file in VS Codeâ€™s explorer and choosing**Downloadâ€¦**. - Go to CS50â€™s Gradescope page.
- Click â€śLab 3: Sortâ€ť.
- Drag and drop your
`answers.txt`

file to the area that says â€śDrag & Dropâ€ť. Be sure it has the correct filename! - Click â€śUploadâ€ť.

You should see a message that says â€śLab 3: Sort submitted successfully!â€ť If you see the message then weâ€™ve received your submission!

Labs are assessed only on whether youâ€™ve submitted an honest attempt.

## Want to see the staff's solution?

```
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.
```