Searching and Sorting: TExES Computer Science 8-12 241
Searching locates data that meets a target condition; sorting arranges data under an ordering rule.
- For the TExES Computer Science 8-12 (241), know how linear and binary search differ, trace common sorts, and connect an algorithm’s cost to its assumptions.
- Binary search requires ordered data, and sorting itself has a cost.
On this page13 sections
- What does a search algorithm do?
- Trace an original binary search
- Compare search costs fairly
- Selection sort: repeatedly choose the next minimum
- Insertion sort: grow a sorted prefix
- Merge sort: divide, sort, and merge
- Quick sort: partition around a pivot
- Stability and duplicate values
- How to trace a sort without losing track
- Work through a selection-sort pass
- Boundary cases are part of the algorithm
- Mistakes that lead to wrong comparisons
- Connect the topic to the 241 exam
The official Computer Science 8-12 (241) framework names linear and binary search, selection, insertion, merge, and quick sort. It also expects candidates to analyze best-, average-, and worst-case efficiencies using informal comparisons and Big-O notation. This guide uses original arrays and traces to explain the core distinctions. It does not copy Pearson’s official sample items.
What does a search algorithm do?
A search algorithm examines data to find a value, determine whether it exists, or locate an item satisfying a condition. A linear search checks elements in sequence and works whether or not the collection is sorted. For an array of n values, a successful search may stop early, but an absent target requires checking every element. Its worst-case comparison count grows linearly with n.
Binary search uses a different strategy. It compares the target with an element near the middle of a sorted sequence. If the target is smaller, it discards the higher half; if it is larger, it discards the lower half. Repeating this process shrinks the search interval geometrically. The number of comparisons grows logarithmically when the data is ordered and the implementation can access a middle element efficiently.
Binary search is not a faster replacement for linear search on arbitrary data. The sequence must be sorted using an order compatible with the comparison, and the data structure must support the access pattern assumed by the algorithm.
Trace an original binary search
Search the sorted array [4, 9, 13, 18, 22, 31, 45] for 22. Use zero-based indexes and a closed interval from low through high. Initially low is 0 and high is 6. The midpoint index is floor((0 + 6) / 2), or 3, whose value is 18. Since 22 is larger, discard indexes 0 through 3 and set low to 4. The remaining interval is indexes 4 through 6.
The next midpoint is floor((4 + 6) / 2), or 5, with value 31. Since 22 is smaller, set high to 4. The only remaining candidate is index 4, value 22, so the search succeeds. Three comparisons find the target. If the target were absent, the interval would eventually become empty, and the implementation would report not found. Be consistent about inclusive bounds: mixing closed and half-open intervals is a common source of off-by-one errors.
| Step | Low | High | Midpoint | Action |
|---|---|---|---|---|
| 1 | 0 | 6 | 3, value 18 | Keep the upper portion |
| 2 | 4 | 6 | 5, value 31 | Keep the lower portion |
| 3 | 4 | 4 | 4, value 22 | Target found |
Compare search costs fairly
Suppose a collection is unsorted and only one lookup is needed. A linear scan may be less work than sorting first and then using binary search. If many lookups will use a stable ordered collection, sorting once and reusing that order can be a sensible trade. If records change often, maintaining order or rebuilding an index also has a cost. A complexity comparison should include the whole task, not just the final lookup.
The representation matters, too. Binary search is efficient on an array because a program can directly access an indexed middle element. On a linked list, reaching the middle requires traversal, so the comparison-count argument does not by itself establish the same total runtime. In an exam question, use the data-structure assumptions stated in the prompt. Do not silently transfer one implementation’s cost model to another.
Selection sort: repeatedly choose the next minimum
Selection sort divides the array into a sorted prefix and an unsorted suffix. On each pass, it scans the suffix to find the smallest remaining value and swaps that value into the next prefix position. For [7, 3, 6, 2], the first pass finds 2 and swaps it with 7, giving [2, 3, 6, 7]. The next pass scans [3, 6, 7]; 3 is already the smallest. Further passes place 6 and 7.
Selection sort performs a quadratic number of comparisons in best, average, and worst cases because it repeatedly scans the remaining suffix even when the input begins sorted. Its swaps can be fewer than its comparisons. This distinction matters if the question asks about writes or swaps rather than comparisons. Selection sort is simple to trace, but the scan pattern makes it unsuitable for large inputs when more efficient alternatives fit.
Insertion sort: grow a sorted prefix
Insertion sort takes the next value and inserts it into the correct position within an already sorted prefix. For [5, 2, 4, 1], start with [5]. Insert 2 before 5 to get [2, 5]. Insert 4 between them to get [2, 4, 5]. Finally, move 1 to the beginning, producing [1, 2, 4, 5]. In an array implementation, values may be shifted to make room for each insertion.
If the input is already sorted, insertion sort makes relatively little work, so its best case is linear under the usual implementation. In average and worst cases, many values may shift across much of the prefix, yielding quadratic growth. It is often useful on small or nearly sorted inputs. State the implementation assumptions when giving precise claims: a linked structure, binary insertion position, and array shifting can change which operation is being counted.
Merge sort: divide, sort, and merge
Merge sort recursively divides a sequence into smaller parts, sorts those parts, then merges sorted sublists by repeatedly choosing the smaller leading value. For [8, 3, 6, 1], divide into [8, 3] and [6, 1], then into one-element lists. Merge [8] with [3] to make [3, 8], and [6] with [1] to make [1, 6]. The final merge compares the front values and produces [1, 3, 6, 8].
A standard merge sort takes O(n log n) time in best, average, and worst cases because it has logarithmic levels of division and linear merging work per level. It generally needs additional space for merging in common array implementations. It is a useful example of a predictable divide-and-conquer algorithm. Exact auxiliary-space behavior depends on implementation details, so do not state a universal memory number without specifying them.
Quick sort: partition around a pivot
Quick sort selects a pivot, partitions the other elements into groups that belong before or after it, then sorts those groups recursively. For [6, 2, 8, 3, 5], choosing 5 as a pivot can partition values into [2, 3], the pivot 5, and [6, 8]. Recursively sorting each side results in [2, 3, 5, 6, 8]. This is a conceptual partition; exact in-place implementations may rearrange values in a different sequence along the way.
With reasonably balanced partitions, quick sort has expected O(n log n) behavior under common assumptions. Highly unbalanced partitions can produce O(n squared) worst-case work. Pivot selection, input patterns, and partition implementation affect performance. It is inaccurate to say quick sort is always O(n log n), or that every version has the same stability and memory properties.
| Algorithm | Core operation | Useful complexity picture | Important qualification |
|---|---|---|---|
| Selection sort | Find minimum in unsorted suffix | Quadratic comparisons | Still scans when already sorted |
| Insertion sort | Insert next value into sorted prefix | Quadratic worst case; linear best case | Nearly sorted input may help |
| Merge sort | Recursively sort and merge | O(n log n) typical standard form | Common implementations use extra merge space |
| Quick sort | Partition around a pivot | Expected O(n log n); worst O(n squared) | Partition balance matters |
Stability and duplicate values
A stable sorting algorithm preserves the relative order of records with equal keys. Imagine sorting student records by last name when records are already ordered by first name. A stable last-name sort keeps the first-name order among students who share a last name. Stability can matter when a sequence is sorted in stages or when equal keys carry meaningful prior order. It is a property of an algorithm and implementation, not a guarantee that applies to every sort bearing a familiar name.
Searching also needs a duplicate policy. If a sorted array contains the target more than once, a basic binary search may return any matching position, depending on its midpoint path. If the task requires the first occurrence or the insertion point, the algorithm must continue searching after a match or use an explicitly defined boundary routine. Read the requested result carefully; “find a match” and “find the first match” are different problems.
How to trace a sort without losing track
- Copy the original sequence and label indexes if positions matter.
- Write the algorithm’s invariant, such as ‘the prefix is sorted.’
- Record the current key, pivot, or minimum before changing values.
- Apply exactly one pass or recursive partition at a time.
- Mark comparisons separately from swaps or shifts when asked for operation counts.
- Check that the final output contains the original values exactly once and is ordered by the requested key.
An invariant is a property that remains true through the algorithm. In insertion sort, after each pass, the prefix processed so far is sorted. In selection sort, each completed prefix contains the smallest values in their final positions. In binary search, if the target exists, it must remain within the current candidate interval. Invariants make a trace easier to verify and expose errors such as discarding a possible match.
Work through a selection-sort pass
Take the sequence [12, 5, 9, 2, 7]. On the first selection-sort pass, compare each value in the unsorted suffix with the current minimum. The smallest is 2, so swap it with the value at the beginning. The sequence becomes [2, 5, 9, 12, 7]. The sorted prefix now contains the smallest value. On the second pass, begin at index 1; 5 is already the smallest of [5, 9, 12, 7], so no swap is needed. Continue until the unsorted suffix has one value.
This trace shows why a sorted prefix is an invariant and why “no swap” does not necessarily mean “no work.” The algorithm still compares the remaining values to establish that 5 is the minimum. To count comparisons, sum the shrinking suffix lengths. For n elements the total is (n - 1) + (n - 2) +... + 1, a quadratic expression. If a question instead asks about swaps, use the swap count, not the comparison count.
Boundary cases are part of the algorithm
A useful trace includes empty and one-element inputs when the algorithm permits them. A search of an empty collection should report no match without attempting to read an element. A one-element sorted array is found immediately if the item matches and otherwise produces an empty remaining interval. For sorting, an empty or one-element sequence is already ordered. These boundary checks expose unsafe midpoint access and recursive routines that omit a terminating base case.
Duplicates create another boundary of meaning. A standard sort may preserve all equal-key records, but a search may stop at any equal item unless its contract says otherwise. If the requested output is the insertion position, the algorithm must define whether new equal values go before or after existing ones. The ordering relation, duplicate behavior, and return value are part of a complete algorithm specification, not minor implementation trivia.
Mistakes that lead to wrong comparisons
- Using binary search on unsorted input.
- Ignoring sort cost when the input begins unordered.
- Claiming quick sort has a guaranteed O(n log n) worst case.
- Saying insertion sort is always quadratic without considering an already sorted input.
- Confusing comparisons with swaps, shifts, or total runtime.
- Forgetting that a duplicate target may have multiple matching positions.
- Assuming all implementations with the same algorithm name have identical stability or space behavior.
- Treating Big O as a precise wall-clock prediction for small arrays.
Connect the topic to the 241 exam
The 241 framework’s Domain III includes algorithm construction and comparison. Competency 009 specifically names linear and binary searching, selection, insertion, merge, and quick sorts, runtime cases, recursion and iteration, and practical algorithm development. Its domain weighting is approximate, not a fixed number of questions. Use the framework to set priorities, then practice tracing and explaining rather than relying only on memorized complexity labels.
The official test page identifies a 100-question selected-response CAT and a five-hour total appointment. A selected-response format does not remove the need to work carefully: code segments, tables, arrays, and stimulus materials can require several state changes before the correct choice becomes apparent. On practice problems, show intermediate arrays and update bounds explicitly. Do not infer an exam score from performance on a small practice set.
Common questions
Does binary search sort the data?
No. Binary search searches a sequence that is already ordered. Sorting is separate work, with its own time and possible memory costs. For a reliable answer, state the relevant assumption and verify it against the official framework or language documentation before applying it to a new example.
Which sort is best?
There is no universal winner. Input size and order, memory, stability, data structure, and implementation constraints matter. Exam scenarios test whether the selected algorithm fits those conditions. For a reliable answer, state the relevant assumption and verify it against the official framework or language documentation before applying it to a new example.
Can quick sort take quadratic time?
Yes. Highly unbalanced partitions can produce quadratic worst-case work, although balanced behavior is commonly O(n log n) under standard assumptions. For a reliable answer, state the relevant assumption and verify it against the official framework or language documentation before applying it to a new example.
What does a stable sort preserve?
It preserves the prior relative order of records whose keys compare equal, provided the selected algorithm and implementation are stable. For a reliable answer, state the relevant assumption and verify it against the official framework or language documentation before applying it to a new example.