Tag: sort

CS50 labs 3 sort

In the cs50 labs 3 sort problem we have to analyze three sorting programs to determine which algorithms they use to sort. These three sorting algorithms are Selection sort, Bubble sort, and Merge sort.

Selection 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

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

Merge sort recursively divides the list into two repeatedly and then merges the smaller lists back into a larger one in the correct order.

Lab Instructions

So there are three compiled programs provided to us, sort1, sort2, and sort3. We have to identify the correct sorting algorithm those three programs use to sort the given datasets.

So we have to run the given datasets (.txt files) as per the given instructions and identify the sorting methods.

./sort1 reversed10000.txt

So my solution for this lab is mentioned below. Considering the time it takes to sort the files, I got the below solution.

sort1 uses: Bubble sort

How do you know?:   When considering the time it takes to sort the sorted50000.txt file for each sort program. Sort1 took
                    the least time to sort the sorted list. That means sort1 uses Bubble sort as the sorting algorithm.

sort2 uses: Merge sort

How do you know?:   When feeding the 3 programs the random50000.txt it took 7.914s for the sort1 program to sort the file.
                    It took 0.654s for the sort2 program to sort the file. And it took 3.534s for the sort3 program to sort
                    the file. So considering the time sort2 got the least time. That means sort2 uses the merge sort!

sort3 uses: Selection Sort

How do you know?:   When considering the time it takes to sort the sorted50000.txt file for each sort program. Sort3 took
                    more time than other two sort programs. That means sort3 uses Selection sort as the sorting algorithm.


time ./sort1 random50000.txt
real 7.914s

time ./sort2 random50000.txt
real 0.654s

time ./sort3 random50000.txt
real 3.534s

time ./sort1 sorted50000.txt
real 0.865s

time ./sort2 sorted50000.txt
real 1.024s

time ./sort3 sorted50000.txt
real 3.273s

You may also like: The solution to CS50 psets 2 substitution problem (2022)