Chunk 3.2: Sorting Algorithms

  • Watch the lecture from 37:25 to 1:01:56. We will cover this material in class as well, so you can skip this portion unless you miss class or need reinforcement of the concepts. In-class slides can be found here.

Questions

  • Answer these questions (submit on Classroom):
    • Describe the Bubble Sort algorithm in your own words (English/pseudocode).
    • Describe the Selection Sort algorithm in your own words (English/pseudocode).
    • Describe the Insertion Sort algorithm in your own words (English/pseudocode).
    • Which Big-O values are considered a “reasonable” run time and which aren’t?

Problem: Selection

  • Implement a program in C in a file named selection.c which accepts any number of random integers as arguments and sorts them using the selection sort algorithm (pdf | video). Your program should print the array each time it makes a change to it (i.e. swapping two elements).
    • Execute wget https://cs-acs.com/assets/source_code/selection.c to download this problem’s distribution code.
    • You will only write the selection_sort() function and should not need to modify any of the other distribution code, though all that matters in the end is that it passes the check50 checks.
    • You don’t have to handle any errors other than what is already implemented in the distribution code.
    • You can assume that all arguments will be positive or negative integers.
    • Your program should only print when it swaps elements, so if you give it an array that is already sorted, it will print nothing.
$ ./selection 5

$ ./selection 1 2 3 4 5 6

$ ./selection -5 10 30 1 5 9 8
-5 1 30 10 5 9 8
-5 1 5 10 30 9 8
-5 1 5 8 30 9 10
-5 1 5 8 9 30 10
-5 1 5 8 9 10 30

$ ./selection 0 1 60 300 67 82
0 1 60 67 300 82
0 1 60 67 82 300

$ ./selection 10 9 8 7 6 5 4 3 2 1                                                                                                                                      
1 9 8 7 6 5 4 3 2 10
1 2 8 7 6 5 4 3 9 10
1 2 3 7 6 5 4 8 9 10
1 2 3 4 6 5 7 8 9 10
1 2 3 4 5 6 7 8 9 10

Check & Submit

Check style with style50:

style50 selection.c

Check functionality with check50:

check50 cs-acs/problems/main/selection

Submit with submit50:

submit50 cs-acs/problems/main/selection