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