Search and Sort

Click Accept lab lab04 at the top of this page → Accept assignment → Open repository → green Code → Codespaces → Create codespace on main. When the terminal shows $:

$ python3 check.py:| search.c finds 50 at index 4: linear in 5 comparisons, binary in 3
...
0/12 checks passed

Read a sorted list of numbers and a target, then search for the target with both algorithms and report the index and the number of comparisons:

$ make search$ ./searchHow many numbers? 7
Number: 1
Number: 5
Number: 10
Number: 20
Number: 50
Number: 100
Number: 500
Target: 50
Linear: found at index 4 after 5 comparisons
Binary: found at index 4 after 3 comparisons

main is mostly written; you print the two result lines (or Linear: not found after 7 comparisons when the target is absent) and fill in the two functions. Both return the index or -1.

The one new thing is the counter. Each function receives int *comparisons, a pointer to the caller’s counter. You do not need to understand pointers yet (that is week 6); you need one idiom: (*comparisons)++; adds one to the counter the caller gave you. Put that line right before every if (numbers[...] == target) and the counts come out right.

For binary search keep two indices, low = 0 and high = n - 1, look at middle = (low + high) / 2, and move low or high past the middle depending on the comparison. The loop runs while low <= high. Trace the example by hand before you run it: 20, then 100, then 50; three comparisons.

Sort a list of numbers with the algorithm named on the command line and print the result on one line:

$ make sort$ ./sort bubbleHow many numbers? 5
Number: 6
Number: 3
Number: 8
Number: 1
Number: 2
1 2 3 6 8

Three things to do, in order:

1. Validate the argument exactly as in caesar.c: one argument, equal to selection or bubble (strcmp(argv[1], "bubble") == 0); otherwise print Usage: ./sort selection|bubble and return 1.
2. Selection sort. For each position i from 0 to n − 2, find the index of the smallest value from i to the end, then swap it into position i. A swap function that takes two pointers is already written for you; call it as swap(&numbers[i], &numbers[smallest]);.
3. Bubble sort. Up to n − 1 passes; in each pass compare every pair of neighbors and swap the ones in the wrong order. Keep a bool swapped; if a whole pass swaps nothing, break.

Print with a space between numbers and no trailing space: printf("%i%s", numbers[i], i < n - 1 ? " " : "\n"); is one way. The tests try duplicates, negative numbers, a single number and a hundred random ones.

Two functions that call themselves:

$ make recursion$ ./recursionHeight: 3
#
##
###
n: 5
5! = 120

draw(n) prints a left-aligned pyramid exactly like the lecture’s recursion.c: if n <= 0 return; otherwise draw(n - 1) first, then one row of n hashes. factorial(n) returns n × (n − 1) × … × 1: the base case is factorial(0) = 1 (and 1 for n = 1), the recursive case is n * factorial(n - 1). Use long, because 20! does not fit in an int; print it with %li. In main, re-prompt while the height or n is outside 0–20.

The checks also read your source: factorial must contain no for or while, and both functions must call themselves. Recursion is the point of this part, not an optional style.

$ git add -A$ git commit -m "Lab 4"$ git push

Your score appears under Releases about two minutes later. Push as often as you like before Friday, October 23, 23:59; the last push before the deadline counts, and late pushes lose 10% per day for up to five days.