Grids, Searching and Sorting

A vector is one row of values. This lesson starts with values that have rows and columns: a table of scores, a map, a picture made of squares.

Then it turns to the two jobs that programs do to a vector most often. Searching is finding where a value is. Sorting is putting the values in order.

Rows of cells

Three teams play four rounds of a quiz. That is twelve scores, and each belongs to a team and to a round. One vector of twelve numbers would lose that shape. A grid keeps it: a vector whose elements are themselves vectors, one for each row.

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> points = {
        {12, 7, 15, 9},
        {10, 14, 8, 12},
        {6, 13, 13, 16}
    };

    std::cout << points[1][2] << "\n";
    std::cout << points.size() << " rows\n";
    std::cout << points[0].size() << " columns\n";

    int rows = points.size();
    int cols = points[0].size();
    int largest = points[0][0];
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            std::cout << std::setw(4) << points[r][c];
            if (points[r][c] > largest) {
                largest = points[r][c];
            }
        }
        std::cout << "\n";
    }
    std::cout << "Largest: " << largest << "\n";
}

8
3 rows
4 columns
  12   7  15   9
  10  14   8  12
   6  13  13  16
Largest: 16

Read the type from the outside in. std::vector<int> is a vector of ints. std::vector<std::vector<int>> is a vector whose elements are vectors of ints. Each inner pair of braces in the list is one row.

• points.size() is the number of rows, 3.
• points[1] is the whole of row 1: a std::vector<int> holding 10, 14, 8 and 12. Rows are counted from 0, like every position.
• points[1][2] takes row 1 first and then position 2 of that row. It is 8. The row comes first, the column second.
• points[0].size() is the size of row 0, which is the number of columns, 4.

A cell is reached with two positions, so visiting every cell takes a loop inside a loop. The outer loop chooses a row. The inner loop runs along the whole of that row before the outer loop moves on. That is why the table is printed row by row.

Notice int rows = points.size(); and int cols = points[0].size();. As module 8 advised, a size is stored in an int before anything is done with it. This lesson does that every time, and every position in it is an int. Later sections need positions that can be -1 and sizes that can have 1 taken away.

A grid can also be made without listing every value. This line makes 3 rows of 4 zeros.

std::vector<std::vector<int>> board(3, std::vector<int>(4, 0));

A grid of characters

A string is already a row of characters, so a vector of strings is a grid of characters. It is the usual way to write a small map or picture straight into a program.

#include "scimigo.h"
#include <string>
#include <vector>
using namespace scimigo;

int main() {
    std::vector<std::string> picture = {
        "..#..#..",
        ".######.",
        "##.##.##",
        "########",
        ".#....#."
    };

    canvas(600, 400);
    int rows = picture.size();
    for (int r = 0; r < rows; ++r) {
        int cols = picture[r].size();
        for (int c = 0; c < cols; ++c) {
            if (picture[r][c] == '#') {
                rectangle(60 + c * 40, 60 + r * 40, 38, 38, "navy");
            }
        }
    }
}

picture[r] is a string, and picture[r][c] is one char of it, so it is compared with a character in single quotes.

In the call to rectangle, the column c decides x, how far to the right, and the row r decides y, how far down. Writing them the other way round turns the picture on its side. It is the commonest mistake with grids.

Reading a grid

A grid can also come from the input. Module 9 read lines until the input ran out with while (std::getline(std::cin, line)). Each line is one row of the grid.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> sky;
    std::string line;
    while (std::getline(std::cin, line)) {
        sky.push_back(line);
    }

    int stars = 0;
    int rows = sky.size();
    for (int r = 0; r < rows; ++r) {
        int cols = sky[r].size();
        for (int c = 0; c < cols; ++c) {
            if (sky[r][c] == '*') {
                ++stars;
            }
        }
    }
    std::cout << rows << " rows, " << stars << " stars\n";
}

..*....*
........
*...*...

3 rows, 4 stars

Here cols is worked out inside the outer loop, from the row itself. Nothing forces the rows of a grid to have the same length, so this is the careful way to write it.

Looking at each element in turn

A cloakroom has numbered tickets on a row of pegs. Which peg holds ticket 44? Without knowing anything about the order, there is one way to find out: look at the first peg, then the second, and so on. This is a linear search.

#include <iostream>
#include <vector>

int index_of(const std::vector<int>& v, int wanted) {
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        if (v[i] == wanted) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::vector<int> tickets = {31, 18, 44, 7, 18, 26};
    std::cout << index_of(tickets, 44) << "\n";
    std::cout << index_of(tickets, 18) << "\n";
    std::cout << index_of(tickets, 50) << "\n";

    int at = index_of(tickets, 7);
    if (at == -1) {
        std::cout << "Ticket 7 is not here\n";
    } else {
        std::cout << "Ticket 7 is on peg " << at << "\n";
    }
}

2
1
-1
Ticket 7 is on peg 3

The answer of a search is a position, not the value. The caller already knows the value.

Follow index_of(tickets, 44). The loop looks at 31, then 18, then 44. The if is true at position 2, and return i; ends the function at once, in the middle of the loop. Positions 3, 4 and 5 are never looked at.

Three things to notice.

• The first match wins. 18 is on pegs 1 and 4. The loop reaches peg 1 first and returns there.
• Absent means -1. For 50 the if is never true. The loop runs out of elements, and only then does the function reach return -1;. No position is negative, so -1 cannot be mistaken for one. This is why the function returns an int and why n is an int: the unsigned size type has no -1.
• return -1; comes after the loop, not in an else. One element that does not match proves nothing. Only when every element has been looked at is the value known to be absent.

How much work is it? Finding the value at position p means looking at p + 1 elements. Finding that a value is absent means looking at all n.

The smallest, and where it is

A search for a known value stops at the first match. Finding the smallest element is different: nothing can be the answer until every element has been seen. The method is to remember the best so far.

#include <iostream>
#include <vector>

int index_of_smallest(const std::vector<int>& v) {
    int best = 0;
    int n = v.size();
    for (int i = 1; i < n; ++i) {
        if (v[i] < v[best]) {
            best = i;
        }
    }
    return best;
}

int main() {
    std::vector<int> degrees = {14, 9, 17, 6, 11, 6};
    int coldest = index_of_smallest(degrees);
    std::cout << "Day " << coldest << "\n";
    std::cout << degrees[coldest] << " degrees\n";
}

Day 3
6 degrees

best is a position. It starts at 0: after looking at one element, that element is the smallest seen. The loop starts at 1 and compares each later element with v[best]. A smaller one becomes the new best.

• The function returns where the smallest is, not what it is. From the position the caller can get the value, as degrees[coldest] does. From the value alone the caller could not get the position without searching again. The next section needs the position.
• The test is <, not <=. The 6 at position 5 is not smaller than the 6 at position 3, so best stays at 3. With equal smallest elements, the first one is reported.
• best starts at 0, so the vector must have at least one element. That is part of the function's contract.
• There is no early return. A vector of n elements always costs n - 1 comparisons.

The same loop can look at only part of a vector, from some later position to the end. The lab asks you to write that version.

Selection sort

To sort a vector is to rearrange its elements into order, here from smallest to largest. Think of sorting a hand of cards laid out in a row. Find the smallest card and exchange it with the card in the first place. The first place is now right for good. Find the smallest of the rest and exchange it with the card in the second place. Carry on. This is selection sort.

Each trip along the vector is called a pass.

#include <iostream>
#include <vector>

void exchange(int& a, int& b) {
    int kept = a;
    a = b;
    b = kept;
}

void print_all(const std::vector<int>& v) {
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

int main() {
    std::vector<int> v = {34, 12, 27, 5, 19};
    print_all(v);

    int n = v.size();
    for (int first = 0; first < n - 1; ++first) {
        int best = first;
        for (int i = first + 1; i < n; ++i) {
            if (v[i] < v[best]) {
                best = i;
            }
        }
        exchange(v[first], v[best]);
        print_all(v);
    }
}

34 12 27 5 19 
5 12 27 34 19 
5 12 27 34 19 
5 12 19 34 27 
5 12 19 27 34

exchange is the function from module 10. Its parameters are references, so exchange(v[first], v[best]) exchanges the two elements themselves.

The inner loop is the best-so-far loop from the section before, started at first and not at 0. Read the output one pass at a time.

1. first is 0. The smallest of all five is 5, at position 3. It is exchanged with the 34 at position 0.
2. first is 1. The smallest from position 1 onwards is 12, which is already at position 1. exchange(v[1], v[1]) exchanges an element with itself, and nothing changes.
3. first is 2. The smallest from position 2 onwards is 19. It is exchanged with 27.
4. first is 3. The smallest of the last two is 27. It is exchanged with 34.

After pass number k, the first k elements are the k smallest, in order, and they are never touched again. The vector is in two parts: a sorted part that grows from the left, and the rest.

The outer loop stops at first < n - 1. Five elements need four passes. When four elements are in their final places, the one that is left is the largest, and it is already last. With an empty vector n - 1 is -1, the test 0 < -1 is false, and no pass runs. That works only because n is an int.

Bubble sort

Bubble sort reaches the same result with a different step. It never looks for the smallest. It walks along the vector comparing each element with its right-hand neighbour, and exchanges the two whenever they are in the wrong order.

#include <iostream>
#include <vector>

void exchange(int& a, int& b) {
    int kept = a;
    a = b;
    b = kept;
}

void print_all(const std::vector<int>& v) {
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

int main() {
    std::vector<int> v = {34, 12, 27, 5, 19};
    print_all(v);

    int n = v.size();
    for (int pass = 1; pass < n; ++pass) {
        for (int i = 0; i < n - pass; ++i) {
            if (v[i] > v[i + 1]) {
                exchange(v[i], v[i + 1]);
            }
        }
        print_all(v);
    }
}

34 12 27 5 19 
12 27 5 19 34 
12 5 19 27 34 
5 12 19 27 34 
5 12 19 27 34

Follow the first pass, one pair at a time.

Once a pass meets the largest element, that element wins every comparison and is carried to the end. So after the first pass the largest element is certainly last. Nothing else is certain: 5, the smallest, has moved only one place to the left.

The second pass does the same for what remains and carries the second largest, 27, to the place before last. After pass number k, the last k elements are in their final places. Here the sorted part grows from the right.

That is why the inner loop's test is i < n - pass. In pass 1 it stops at i < 4, so the last pair compared is v[3] and v[4], the last two elements. In pass 2 it stops one pair earlier, because the last element no longer needs comparing. The test also keeps v[i + 1] inside the vector: the largest i is n - pass - 1, so i + 1 is at most n - 1.

The fourth pass changed nothing. The vector was already sorted after the third, and the program did not know. A homework task makes bubble sort notice.

Halving the range

Somebody thinks of a number from 1 to 100 and answers each guess with "higher" or "lower". Nobody guesses 1, 2, 3 in turn. They guess 50, and one answer removes half the numbers. Then they guess the middle of what is left.

A program can search a vector the same way, on one condition: the vector is sorted. Then looking at one element says on which side the wanted value must be. This is a binary search. The version below prints what it looks at, so that the method can be seen.

#include <iostream>
#include <vector>

int position_in_sorted(const std::vector<int>& v, int wanted) {
    int n = v.size();
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        std::cout << "  low " << low << ", high " << high << ": v[" << mid << "] is " << v[mid] << "\n";
        if (v[mid] == wanted) {
            return mid;
        }
        if (v[mid] < wanted) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<int> v = {2, 5, 9, 14, 20, 21, 28, 33, 37, 45, 52};
    std::cout << "Looking for 33\n";
    std::cout << position_in_sorted(v, 33) << "\n";
    std::cout << "Looking for 10\n";
    std::cout << position_in_sorted(v, 10) << "\n";
}

Looking for 33
  low 0, high 10: v[5] is 21
  low 6, high 10: v[8] is 37
  low 6, high 7: v[6] is 28
  low 7, high 7: v[7] is 33
7
Looking for 10
  low 0, high 10: v[5] is 21
  low 0, high 4: v[2] is 9
  low 3, high 4: v[3] is 14
-1

low and high are two positions. Between them, both included, lie the only elements that could still be the wanted one. At the start that is the whole vector, from 0 to n - 1.

Each turn of the loop looks at the middle of the range. (low + high) / 2 is int division, so with an even number of candidates it picks the left of the two middle ones. Then one of three things is true.

• v[mid] is the wanted value. Return its position.
• v[mid] is too small. The vector is sorted, so everything to the left of mid is smaller still. The answer can only be to the right: low = mid + 1.
• v[mid] is too large. By the same argument the answer can only be to the left: high = mid - 1.

Follow the search for 33. The first look, at 21, removes six elements at once: positions 0 to 5. The second, at 37, removes positions 8 to 10. The fourth look finds it. A linear search would have looked at eight elements.

Three details decide whether a binary search is right.

• mid + 1 and mid - 1, not mid. Position mid has been looked at and is not the answer, so it leaves the range. This also means the range gets smaller on every turn. With low = mid the range could stay the same for ever.
• while (low <= high), not <. When low equals high there is still one candidate, and it has not been looked at. The search for 33 ends on exactly such a turn.
• The loop ends when low passes high. Then the range is empty and the value is absent. The search for 10 ends with low 3 and high 2.

For an empty vector high starts at -1, the test 0 <= -1 is false, and the function returns -1 without looking at anything. An unsigned high could not hold -1.

Binary search trusts the order and does not check it. Given a vector that is not sorted, it can step past a value that is present and report -1.

Counting the work

Which sort is faster? Which search? Timing a program gives a different answer on every computer. Counting its comparisons gives the same answer everywhere.

To count, give the function one more parameter: a counter, passed by reference, that the function adds to. bubble_sort below adds 1 for every pair it compares.

#include <iomanip>
#include <iostream>
#include <vector>

void exchange(int& a, int& b) {
    int kept = a;
    a = b;
    b = kept;
}

void bubble_sort(std::vector<int>& v, int& comparisons) {
    int n = v.size();
    for (int pass = 1; pass < n; ++pass) {
        for (int i = 0; i < n - pass; ++i) {
            ++comparisons;
            if (v[i] > v[i + 1]) {
                exchange(v[i], v[i + 1]);
            }
        }
    }
}

int halvings(int n) {
    int steps = 0;
    while (n > 0) {
        n = n / 2;
        ++steps;
    }
    return steps;
}

int main() {
    std::cout << "    size    bubble sort    halvings\n";
    for (int size = 8; size <= 64; size = size * 2) {
        std::vector<int> v;
        for (int i = 0; i < size; ++i) {
            v.push_back(size - i);
        }
        int comparisons = 0;
        bubble_sort(v, comparisons);
        std::cout << std::setw(8) << size << std::setw(15) << comparisons
                  << std::setw(12) << halvings(size) << "\n";
    }
    std::cout << "Halvings of 1000: " << halvings(1000) << "\n";
    std::cout << "Halvings of 1000000: " << halvings(1000000) << "\n";
}

    size    bubble sort    halvings
       8             28           4
      16            120           5
      32            496           6
      64           2016           7
Halvings of 1000: 10
Halvings of 1000000: 20

main owns the variable comparisons, sets it to 0, and passes it. Inside the function, ++comparisons changes main's variable, because the parameter is an int&. The function only adds to the counter. Setting it to 0 is the caller's job, so one counter can also add up several calls.

What one comparison is. In a sort, one comparison is one pair of elements compared with each other. In a search, one comparison is one element of the vector compared with the wanted value: one look. A binary search asks two questions about v[mid] in one turn of its loop, == and then <. Both are about the same element, so together they are one comparison. A search that counts its work therefore adds 1 once in each turn of its loop. A test of an element made outside the loop, such as a look at the first element before the loop starts, is one more comparison.

Bubble sort. The first pass over n elements compares n - 1 pairs, the next n - 2, and so on down to 1. For 8 elements that is 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28. Each time the size doubles, the count becomes about four times as large: twice as many passes, and each pass about twice as long.

Halvings. halvings(n) counts how often n can be halved before nothing is left. That is the largest number of comparisons a binary search of n elements can need, since every look halves the range. Doubling the size adds one. A thousand elements need at most 10 comparisons, and a million need at most 20. A linear search of a million elements may need a million. The price of the fast search is that the data must be sorted first.

The library's sort

Sorting is needed so often that the standard library does it for you. The function is std::sort, and its header is <algorithm>.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<int> ages = {41, 17, 68, 17, 5, 30};
    std::sort(ages.begin(), ages.end());
    for (int age : ages) {
        std::cout << age << " ";
    }
    std::cout << "\n";

    std::vector<std::string> towns = {"leeds", "York", "bath", "Hull", "Ely"};
    std::sort(towns.begin(), towns.end());
    for (const auto& town : towns) {
        std::cout << town << " ";
    }
    std::cout << "\n";
}

5 17 17 30 41 68 
Ely Hull York bath leeds

std::sort is given two things: where to start and where to stop. ages.begin() means the start of the vector and ages.end() means its end. Together they say "from the start to the end", which is all of it. For now, always write the pair exactly like this, with the same vector's name in both.

• It sorts the vector itself. It gives nothing back, so there is nothing to store: the call stands on its own as a statement.
• Equal values are all kept. Both 17s are in the result.
• It sorts anything that < can compare. For strings, < is the comparison from module 8, character by character, with every capital letter before every small one. That is why York comes before bath.
• Forgetting #include <algorithm> is a compile error in the lab, even where another compiler lets it pass.

std::sort is also much faster than the two sorts above. For a million elements, selection sort makes about five hundred billion comparisons and std::sort about twenty million, by a cleverer method. Writing the two simple sorts is practice in loops that rearrange a vector. In a real program, call std::sort.

Sorting and binary search belong together. Sort the data once, and after that every search costs a handful of looks.