Introduction to Computer Science: Harvard CS50 · Course book
Chapter 3: Many Values, and Putting Them in Order
A single variable holds a single value. Real programs handle many values at once: every score in a class, every letter in a word, every name in a list. This chapter introduces the array, the simplest way to store many values together, and shows that text in C is nothing more than an array of characters. It then looks at what happens when you compile, at how programs receive input from the command line, and at a central question of computer science: how to sort a list, and how to tell a fast method from a slow one.
What compiling really involves
Chapter 2 treated compiling as one step. It is really four, carried out one after another.
| Step | What happens | Example |
|---|---|---|
| Preprocessing | Lines beginning with # are replaced by the contents they refer to | #include <stdio.h> pulls in the declaration of printf |
| Compiling | C is translated into assembly language, low-level instructions written as text | Instructions such as "move this value into a register" |
| Assembling | Assembly is translated into machine code, the binary the processor runs | Patterns of 0s and 1s |
| Linking | Your machine code is combined with the machine code of libraries you used | The code that actually implements printf is joined to yours |
When a program compiles but behaves wrongly, the fault is a bug, and finding it is debugging. Three tools cover most needs: reading the compiler's error messages carefully, adding temporary printf lines to show what variables contain, and using a debugger, a program that lets you pause your code at any line and step through it one statement at a time while watching the variables change. Explaining your code aloud, line by line, to a friend or even to a rubber duck on your desk, often reveals the mistake as you say it.
Arrays: many values under one name
Suppose a program averages three test scores. With separate variables it needs score1, score2 and score3, which becomes unwieldy at thirty scores. An array stores them together, side by side in memory, under one name.
int scores[3];
scores[0] = 72;
scores[1] = 73;
scores[2] = 33;
printf("Average: %f\n", (scores[0] + scores[1] + scores[2]) / 3.0);
The number in square brackets is the index, and indexes start at 0, so an array of 3 elements uses indexes 0, 1 and 2. The average is (72 + 73 + 33) ÷ 3.0 = 178 ÷ 3.0 = 59.33. Dividing by 3.0 instead of 3 keeps the fraction, for the reason seen in Chapter 2. A loop makes the code work for any number of scores: for (int i = 0; i < n; i++) adds up scores[i] one by one.
C does not check whether an index is valid. Asking for scores[3] in an array of three reads whatever happens to be in the next spot in memory, which may be garbage or may crash the program. Staying within bounds is the programmer's job.
Strings are arrays of characters
A string is an array of chars, one per character, followed by one extra byte holding the value 0, written \0 and called the null character. It marks where the string ends. The string "HI!" therefore takes four bytes, not three.
Because characters are numbers, text can be manipulated with arithmetic. In ASCII, lower-case letters are exactly 32 more than their capitals: 'a' is 97 and 'A' is 65. Subtracting 32 from a lower-case letter therefore makes it upper case. A loop that walks through a string until it reaches \0, converting each letter in the range 'a' to 'z', capitalises the whole word.
The same idea underlies simple cryptography. A Caesar cipher shifts every letter a fixed number of places: with a shift of 1, "HI" becomes "IJ", because 72 + 1 = 73 and 73 + 1 = 74. The receiver shifts back to decrypt. Such ciphers are trivially broken, since there are only 25 useful shifts to try, but they show that encryption is, at heart, arithmetic on numbers that stand for letters.
Programs can also receive input at the moment they are run, as command-line arguments. Declaring main as int main(int argc, string argv[]) gives the program argc, the number of words typed, and argv, an array of those words. Running ./caesar 3 makes argc equal to 2, with argv[0] holding "./caesar" and argv[1] holding "3". When main finishes, it returns an exit code to the system: 0 by convention means success, and any other number signals a particular error.
Searching an array follows the same two patterns as the phone book. Linear search checks each element in turn and works on any array. Binary search repeatedly compares the target with the middle element and discards half, and works only when the array is sorted. In code, binary search keeps two indexes marking the part of the array still in play, and moves one of them past the middle at every step until the target is found or the two indexes cross.
Sorting
Chapter 1 showed that a sorted list can be searched dramatically faster than an unsorted one. Sorting has a cost of its own, though, and methods differ enormously. Take the list 5, 2, 7, 4, 1, 6.
Bubble sort walks along the list comparing neighbours and swapping any pair in the wrong order, then repeats. After the first pass the largest value, 7, has "bubbled" to the end: 2, 5, 4, 1, 6, 7. After the second pass: 2, 4, 1, 5, 6, 7. After the fourth the list is sorted, and a pass with no swaps confirms it.
Selection sort finds the smallest value and swaps it into the first position, then finds the smallest of the rest for the second position, and so on. The first pass picks 1, giving 1, 2, 7, 4, 5, 6; the second leaves 2 in place; the third moves 4 forward; and after five passes the list reads 1, 2, 4, 5, 6, 7.
Merge sort takes a different approach. Split the list in half, sort each half (by splitting again, until single items remain), then merge the sorted halves by repeatedly taking the smaller front item of the two. Merging 2, 5, 7 with 1, 4, 6 takes 1, then 2, then 4, then 5, then 6, then 7.
Follow merge sort through the whole list. Split 5, 2, 7, 4, 1, 6 into 5, 2, 7 and 4, 1, 6. Split each again, into 5 and 2, 7, and into 4 and 1, 6. The single items 5 and 4 are already sorted. Merging 2 with 7 gives 2, 7, and merging 1 with 6 gives 1, 6. Climbing back up, merging 5 with 2, 7 gives 2, 5, 7, and merging 4 with 1, 6 gives 1, 4, 6. The final merge, shown above, produces 1, 2, 4, 5, 6, 7.
Merge sort is recursive: its instructions include using merge sort itself on smaller lists. That sounds circular, but it is not, because every call works on a shorter list, and a list of one item needs no work at all. That simplest case, called the base case, is what stops the recursion. Many elegant algorithms are written this way, and Chapter 5 returns to recursion when building data structures.
The difference shows when the list grows. Bubble and selection sort compare roughly every pair of items, about n × (n − 1) ÷ 2 comparisons: 28 for 8 items but 499,500 for 1,000. Merge sort halves the list about log₂ n times and does about n work at each level, roughly n × log₂ n in all: 24 for 8 items and about 10,000 for 1,000.
| Algorithm | Worst case, O | Best case, Ω | Note |
|---|---|---|---|
| Linear search | n | 1 | Works on any list |
| Binary search | log n | 1 | The list must be sorted |
| Bubble sort | n² | n | Can stop early if a pass makes no swaps |
| Selection sort | n² | n² | Always scans the rest of the list |
| Merge sort | n log n | n log n | Needs extra memory for merging |
The notation in Table 3.2 describes growth, ignoring constant factors. O, "big O", gives an upper bound, the worst case; Ω, omega, gives a lower bound, the best case. When the two agree, as for merge sort, the running time is written with Θ, theta.
Check your understanding
- Name the four steps of compiling in order.
- An array has 10 elements. What are its first and last indexes? (Answer: 0 and 9.)
- How many bytes does the string "CS50" occupy? (Answer: 5, including the null character.)
- What is the ASCII value of lower-case 'h', given that 'H' is 72? (Answer: 104.)
- Encrypt "CAB" with a Caesar shift of 2. (Answer: "ECD".)
- Running ./program one two gives what value of argc? (Answer: 3.)
- About how many comparisons does selection sort make on 100 items, and merge sort? (Answer: about 4,950, against about 660.)
This course book is available to read online only at tech-academy.chrysolites.org.