Chrysolites Tech Academy

Introduction to Computer Science: Harvard CS50 · Course book

Chapter 3: Many Values, and Putting Them in Order

Pairs with Lesson 3: Arrays, Strings and Sorting Algorithms

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.

StepWhat happensExample
PreprocessingLines beginning with # are replaced by the contents they refer to#include <stdio.h> pulls in the declaration of printf
CompilingC is translated into assembly language, low-level instructions written as textInstructions such as "move this value into a register"
AssemblingAssembly is translated into machine code, the binary the processor runsPatterns of 0s and 1s
LinkingYour machine code is combined with the machine code of libraries you usedThe 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.

HI!\0 7273330 [0][1][2][3] null charactermarks the end The string "HI!" in memory Character, its ASCII value, and its index in the array
Figure 3.1 — A string is a row of bytes. Three characters need four bytes, because the final null character tells functions where the string stops.

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.

bubble, selection: about n² ÷ 2merge sort: about n log₂ n 0400800 0816243240items in the list comparisons needed
Figure 3.2 — Comparisons needed by two families of sorting algorithm. At 40 items the gap is already almost four to one; at a million items it is about 25,000 to one.
AlgorithmWorst case, OBest case, ΩNote
Linear searchn1Works on any list
Binary searchlog n1The list must be sorted
Bubble sortn²nCan stop early if a pass makes no swaps
Selection sortn²n²Always scans the rest of the list
Merge sortn log nn log nNeeds 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.)

Install Chrysolites Tech Academy

Android / Chrome / Edge: open the browser menu and choose Install app or Add to Home screen.

iPhone / iPad (Safari): tap the Share button, then Add to Home Screen.