Searching, sorting, and preserving records

Searching asks where a value occurs. Sorting asks what order the values should have. These are different tasks: a search can leave the collection unchanged, while a sort rearranges it. Before doing either, identify the active elements. An array may have room for ten values while only its first three positions contain data for this task.

An index is a position number. In a three-element array, the indices are 0, 1, and 2. The value at index 1 might be 2; the index and the stored value happen to be different numbers. Keeping that distinction clear is the first step in reading a search result.

Follow one linear search #

A linear search visits the active elements one at a time. It can stop when it finds the target. If it reaches the end without a match, it needs a separate way to report failure. Here that failure result is -1, which is outside the valid index range.

#include <iostream>

int find_index(const int values[], int used, int target) {
    for (int i = 0; i < used; ++i) {
        if (values[i] == target) return i;
    }
    return -1;
}

int main() {
    const int values[] = {7, 2, 9};
    std::cout << find_index(values, 3, 2) << ' '
              << find_index(values, 3, 5) << '\n';
}

Start with the function's inputs. values gives access to the integers, used says how many are active, and target is the value being sought. The const says this function will not change those integers through its array parameter. The function does not know the allocation's size by itself. Its caller must supply a nonnegative count that fits the actual array.

The first call asks for 2. The loop begins with i equal to 0, compares 7 with 2, and continues because they differ. The increment makes i equal to 1. Now the comparison is 2 with 2. The function returns 1 immediately: the matching position. A return leaves the function, so it does not examine 9 afterward.

The second call asks for 5. Its comparisons are 7 with 5, 2 with 5, and 9 with 5. None match. After the third increment, i is 3. The condition i < used is false, the loop ends, and the function returns -1. The output is 1 -1.

The caller must check before using a result as an index. index >= 0 separates these two outcomes for this interface. Testing only if (index) would fail: index zero is a valid success, but zero is false in a condition. Meanwhile -1 is nonzero and would be treated as true. If duplicate targets exist, this function returns the first matching index because it stops at the first match.

Put one value in place at a time #

Selection sort repeatedly finds the smallest remaining value and moves it into the next position. The remaining part is called the unsorted range; the part already placed at the beginning is the sorted prefix.

Take [7, 2, 9]. For the first position, compare all three values. The smallest is 2, at index 1. Exchange positions 0 and 1, giving [2, 7, 9]. The first position now contains the smallest value in the collection. For the second position, examine only [7, 9]. Its smallest value is already first in that remaining range, so there is no useful exchange to make.

A pass numbered i starts by treating i as the minimum's index. A second index j examines positions from i + 1 through used - 1. Finding a smaller value changes the saved minimum index. It does not exchange elements yet. Make the exchange once, after the scan has established which value belongs at position i.

Why use a temporary value or std::swap? Writing one value over another can destroy the value still needed for the other position. std::swap, declared by <utility>, performs the exchange without that loss. The rule preserved after each pass is called an invariant: the prefix contains the smallest selected values in sorted order.

Bubble sort uses another rule. It compares neighboring values and exchanges a pair when the left one is larger. On [7, 2, 9], comparing 7 and 2 gives [2, 7, 9]; comparing 7 and 9 leaves them alone. A full pass moves a largest remaining value toward the end. A pass with no exchanges establishes that every adjacent pair is in order. These simple sorts generally make a number of comparisons that grows roughly with the square of the collection's size.

Sorted values and records #

Binary search discards part of a search range after examining its middle. This depends on the values already being sorted: their order justifies deciding which half can contain the target. A library search or sort also has a contract, including valid ranges and required ordering.^[1]

The median is the middle of ordered data. With an odd positive used, index used / 2 identifies the middle value. With an even positive count, average positions used / 2 - 1 and used / 2. For [2, 5, 8, 11], those positions are 1 and 2, containing 5 and 8. Their average is 6.5. Use floating-point arithmetic so integer division does not discard the fraction. An empty collection has no middle value.

Sorting records needs one more check. Suppose parallel arrays contain names and quantities: one index means one item's name and its quantity. Exchanging only quantities attaches them to the wrong names. Exchange every associated field together, or group the fields in a structure so moving one record moves them all.

Practice with explained answers #

Trace selection sort on [4, 1, 3, 1]. The first selected minimum is the 1 at index 1, producing [1, 4, 3, 1]. The next scan finds the 1 at index 3 and produces [1, 1, 3, 4]. Neither duplicate is discarded. A search for 1 now returns index 0 with this search function.

Test an empty range, one element, already sorted input, reversed input, repeated values, and a missing target. Each case checks a different boundary: no loop iterations, no exchange needed, correct comparison direction, duplicate preservation, or failure reporting. These ideas prepare CS2 Lecture 5 and the median and inventory work in Labs 2 and 3.