C language: sorting lab

We continue the course cs50, week three, sorting algorithms. It’s time for the lab. It is very simple:

  • download test setup: https://cdn.cs50.net/2021/fall/labs/3/sort.zip
  • inside the archive there are three already compiled C programs: sort1, sort2 and sort3 are binaries, i.e. binary code files, so we can’t view their C source code.
  • each of these programs works on one of the sorting algorithms: selection sort, bubble sort, or merge sort. In what file what – we do not know. Our task is to determine which sorting algorithm is used in each binary..

In this task, you need to understand which program uses which algorithm, and you need to do this regardless of the program code itself, since it is not visible, but only by the time it takes to sort different data arrays. To do this, we are given several .txt files that contain numbers – there are three types of files:

  1. already sorted correctly;
  2. random order;
  3. sorted in reverse order.

The files have from 5 to 50 thousand values, and we can run each of the three programs for each of these 9 files with numbers, the launch of the sort program goes through the command line: ./[program_name] [text_file.txt]

For example, a run might look like this:
./sort1 reversed50000.txt.

To find out how long it will take the program to sort, start the timer through the terminal:
time ./[program_name] [text_file.txt].

We write down the real time value for ourselves, and use this data to analyze the algorithms. To pass the laboratory work, you need to fill in the answer.txt text file – write which program uses which algorithm and explain why you made such a conclusion. There is no need to write the code of the algorithms itself or to program anything at all. The task is reduced to analysis and logical search for an answer.


To complete this lab, I drew a table and filled it with data.:

Since we don’t have any data other than the sorting execution time, we need to look at the time and analytically guess which algorithm is which. Given that different algorithms have different minimum and maximum times, I initially focused on comparing the data from the first column (reversed) and the last column (sorted): these are our worst and best cases. Worst, since all data is sorted backwards. And the best, since all the numbers are in the right order anyway.

First, I found those two algorithms where the worst and best cases differ little, since their execution time is close (selection and merge), then from there I found an algorithm that becomes noticeably slower as the number of the reverse sorted array increases (bubble). Further, how to distinguish selection from merge? Merge sorts faster than select when increasing the amount of data. In the end, I compared how the algorithm behaves in general, even if the numbers are random. As a result, at first I found a bubble, and then I selected merge from the remaining two.

sort1 uses: bubble sort

How do you know?: reversed and sorted speed soring is different (as n^2 and n) and for the biggest random list it is the slowest

sort2 uses: merge sort

How do you know?: it has the same or close sorting speed for best and worst cases and it much faster than 3rd (as nlogn)

sort3 uses: selection sort

How do you know?: it has the same or close sorting speed for reversed and sorted lists, but it become slower with growing of numbers (as n^2)


Well, I used a no less archaic way – a notepad 🙂 The following results were obtained:

sort 1 - slowest on random and reversed, but good at sorted
bubble sort

random 5000     .092
random 10000    .254
random 50000   8.145

reversed 5000   .089
reversed 10000  .285
reversed 50000 6.362

sorted 5000     .027
sorted 10000    .087
sorted 50000    .552


sort 2 - faster than any other for all types of data
merge sort

random 5000     .041
random 10000    .266
random 50000    .486

reversed 5000   .038
reversed 10000  .083
reversed 50000  .562

sorted 5000     .044
sorted 10000    .069
sorted 50000    .506


sort 3 - equal on any type of data
selection sort
random 5000     .070
random 10000    .179
random 50000    3.790

reversed 5000    .076 
reversed 10000   .206
reversed 50000  3.744

sorted 5000      .047
sorted 10000     .172
sorted 50000    3.465

See you on new labs!

This entry was posted in C language (en). Bookmark the permalink.

Leave a Reply

🇬🇧 Attention! Comments with URLs/email are not allowed.
🇷🇺 Комментарии со ссылками/email удаляются автоматически.