Linear search (線形探索法) checks the data from the start, one item at a time, against the target value and stops as soon as it finds a match.
Compare with 4 (1st)
Compare with 9 (2nd)
7 (3rd) matches: stop
The 3rd comparison matches, so the search ends without checking the remaining 2.
3 / 3
It works on data as it is, even if the data has not been sorted. The number of comparisons depends on where the target sits, and if it is last or missing altogether, every item gets compared. On average it takes about half as many comparisons as there are items.
AnalogyIt is like hunting for a book on an unordered shelf by checking each spine from the left end, one book after another.
How to remember"Linear" means along a line: you trace it from one end in a single direction.
Exam points
ExamIn linear search (線形探索法) the number of comparisons grows in proportion to the number of items. Double the items and the worst-case comparisons double too.
Binary search (2分探索法) works on sorted data, in increasing (ascending) or decreasing (descending) order, and compares the target with the value in the middle of the range, keeping only the half where the target must be.
Range: items 1–8
Compare with middle item 4 (13)
Narrow to items 5–8
Middle item 6 (21) matches
The 6th value, at the middle of the new range, is 21, so it is found in 2 comparisons.
4 / 4
With ascending data, you keep only the first half when the target is smaller than the middle value and only the second half when it is larger, repeating until you find it or the range is empty. Each comparison removes about half of the candidates, so doubling the number of items adds only about one comparison. The count still depends on where the target sits, though, and a value near the start can be found in fewer comparisons by linear search.
AnalogyIt is like pulling the middle slip from a stack of numbered tickets, deciding whether your number comes before or after it, and then checking the middle of the half that remains.
How to rememberThe "binary" in binary search means "two": every step cuts the range in two.
Exam points
ExamBinary search (2分探索法) keeps comparing the target with the middle element of the remaining range, cutting the candidates roughly in half with each comparison.
Mix-upIt is binary search (2分探索法) that requires data already sorted in ascending (昇順) or descending (降順) order, while linear search (線形探索法) works whatever the order.
Selection sort (選択ソート) repeatedly picks the smallest value (or the largest) from the part not yet sorted and swaps it with the value at one end of that part.
Start 6 2 9 4
Pass 1 2 6 9 4
Pass 2 2 4 9 6
Pass 3 2 4 6 9 (last one fixed too)
Pass 3 swaps 6, the smaller of the remaining 9 6, with the 9 in position 3, fixing position 3, and the last 9 lands in position 4 without any comparison.
4 / 4
Sorting means rearranging data in order of value. One round that scans the unsorted range and fixes the value at one end is called a pass, and each pass shrinks the range by one. The number of comparisons grows roughly with the square of the number of items, so large data sets take a long time.
AnalogyIt is like tidying a hand of cards: find the lowest card among those not yet arranged, place it just to the right of the arranged ones, and repeat.
How to rememberSelection means picking out: like choosing a team captain, you compare everyone first and then pick one.
Exam points
ExamEach pass of selection sort (選択ソート) fixes one position at one end, and the last remaining item needs no comparison to fall into place. The number of passes equals the number of items if the procedure counts that last item as a pass, and the number of items − 1 if it does not.
ExamIn a selection sort that moves the minimum to the front, once the k-th selection and swap are done, the first k values are fixed in increasing order.
Bubble sort (バブルソート) compares two neighbouring values, swaps them if they are out of order, and repeats this from one end to the other.
Start 6 2 9 4
Swap 6 and 2 → 2 6 9 4
Keep 6 and 9 → 2 6 9 4
Swap 9 and 4 → 2 6 4 9
Swapping items 3 and 4 carries the largest value, 9, to the end, fixing position 4.
4 / 4
When sorting into ascending order, each pass carries the largest value to the end, where it stays. The next pass does the same over the range minus that fixed end, and if a whole pass makes no swaps, the data is already sorted. As with selection sort, the number of comparisons grows roughly with the square of the number of items.
AnalogyIt is like people in a row comparing height only with the person next to them, the taller one stepping one place to the right, all the way to the end of the row.
How to rememberA bubble rises: the large values float up to the end one at a time.
Exam points
ExamAn ascending bubble sort (バブルソート) swaps two neighbours when the left one is larger. Each pass fixes the value at the end, so the next pass compares over a range one item shorter.
Mix-upSelection sort (選択ソート) finishes finding the minimum in a pass and then swaps at most once, while bubble sort (バブルソート) swaps out-of-order neighbours on the spot at every comparison.
Quick sort (クイックソート) chooses one pivot value, splits the data into a group smaller than it and a group larger than it, and repeats the same steps on each group.
5 8 2 7 1 4 (pivot 5)
Smaller group 2 1 4 (pivot 2)
1
2
4
5
Larger group 8 7 (pivot 8)
7
8
Each group is split by its own pivot, and a value is fixed once it stands alone. Read from left to right, the result is 1 2 4 5 7 8.
3 / 3
Once a group has one element or none, there is nothing left to split, and lining up the groups in order sorts the whole set. Applying the same procedure to smaller and smaller parts like this is called recursion. On average it needs fewer comparisons than the square-type methods, but a poor choice of pivot pushes the count toward the square of the number of items.
AnalogyIt is like splitting a pile of papers into those dated before a reference date and those after it, then splitting each pile the same way again.
How to rememberQuick, as the name says: on average it is fast.
Key points
Searching (探索) finds where a target value sits in the data, and sorting (整列) rearranges the data in order of value.
Selection sort and bubble sort both fix one value's position from an end with each pass, and their comparisons grow roughly with the square of the number of items.
Quick sort splits the data into smaller and larger groups around a pivot and repeats the same steps on each group. On average it needs fewer comparisons than the square-type methods.