# Searching and sorting ideas

Physics I · Computer Science · https://tryals.app/learn/physics-i/searching-and-sorting-ideas

## Searching Data

Finding data efficiently is fundamental in computational physics, from grid tracking to sorting eigenvalues.

**Linear search** checks every element sequentially. Cost: $O(n)$.

**Binary search** repeatedly halves the search space. Cost: $O(\log n)$. For 1 billion sorted elements, it takes only about 30 comparisons.

| Algorithm | Time Cost | Precondition |
| --- | --- | --- |
| **Linear** | $O(n)$ | None |
| **Binary** | $O(\log n)$ | **Sorted** array |

> **Common pitfall:** Binary search demands sorted input. On unsorted data, it fails silently and returns wrong answers. Fast algorithms buy speed with preconditions.

## Sorting Algorithms

The efficiency of sorting is measured by comparisons relative to input size $n$. The **lower bound** for comparison sorting is $\Omega(n \log n)$.

| Algorithm | Average Cost | Stable? |
| --- | --- | --- |
| **Bubble sort** | $O(n^{2})$ | Yes |
| **Merge sort** | $O(n\log n)$ | Yes |
| **Quick sort** | $O(n\log n)$ | No |

- **$O(n^{2})$** algorithms compare every pair.
- **$O(n \log n)$** algorithms use divide-and-conquer.

In practice, use Python's built-in `sorted()` or `np.sort()`, which use optimised $O(n\log n)$ algorithms.

## Practice questions

6 of this lesson's 14 practice questions, with answers. The full set is in the app.

### 1. Trace **selection sort** on the list [7, 2, 9, 1]. Order the states the list passes through.

**Answer:**

1. [7, 2, 9, 1], initial list
2. [1, 2, 9, 7], smallest (1) swapped to front
3. [1, 2, 9, 7], 2 already in place, no change
4. [1, 2, 7, 9], 7 swapped into third place

**Why:** Selection sort grows a sorted prefix one guaranteed-correct element per pass, simple to reason about, but each pass rescans the whole tail: $O(n^{2})$ total. Understanding **why** it is slow is the first step toward appreciating faster sorts.

Page: https://tryals.app/practice/physics-i/searching-and-sorting-ideas/trace-selection-sort-on-the-list-7-2-9-1-order-the-states-the

### 2. Classify each sort as O($n^{2}$) average or O(n log n) average.

**Answer:**

- O($n^{2}$): Bubble sort, Insertion sort, Selection sort
- O(n log n): Merge sort, Quick sort (avg)

**Why:** Divide-and-conquer sorts achieve O(n log n); simple nested-loop sorts are O($n^{2}$).

Page: https://tryals.app/practice/physics-i/searching-and-sorting-ideas/classify-each-sort-as-o-n-average-or-o-n-log-n-average

### 3. You guess a number between 1 and 1000; after each guess you learn "higher" or "lower". A smart player needs at most **10 guesses**. What strategy achieves this?

A. Start at 1 and count upward
B. Guess multiples of 100 first, then narrow down
C. Always guess the middle of the range
D. Guess randomly to avoid worst cases

**Answer:** C. Always guess the middle of the range

**Why:** Binary search: each middle guess halves the search space, so 1000 candidates fall in $\log_2 1000 \approx 10$ steps. The same idea finds words in dictionaries, entries in databases, and bugs in version history (`git bisect`), provided the data is **sorted**.

Page: https://tryals.app/practice/physics-i/searching-and-sorting-ideas/you-guess-a-number-between-1-and-1000-after-each-guess-you-learn

### 4. Binary search is far faster than linear search but is used less often in practice. Why is it used less often than its speed would suggest?

A. It is only correct for numerical data, not for text
B. It requires the data to be sorted, which costs more
C. It fails when the target is absent from the collection
D. It uses more memory than a linear scan

**Answer:** B. It requires the data to be sorted, which costs more

**Why:** The precondition is the cost. Sorting is $O(n\log n)$ and a scan is $O(n)$, so for one lookup the scan wins, binary search pays off across repeated queries.

Page: https://tryals.app/practice/physics-i/searching-and-sorting-ideas/binary-search-is-far-faster-than-linear-search-but-is-used-less-often

### 5. Order the steps of merge sort on [3, 1, 4, 2].

**Answer:**

1. Split into [3,1] and [4,2]
2. Split further into [3],[1] and [4],[2]
3. Merge pairs: [1,3] and [2,4]
4. Merge final halves: [1,2,3,4]

**Why:** Merge sort recursively splits, then merges sorted sub-arrays bottom-up.

Page: https://tryals.app/practice/physics-i/searching-and-sorting-ideas/order-the-steps-of-merge-sort-on-3-1-4-2

### 6. Binary search finds a name among 1,000 sorted entries in ~10 steps. Estimate the steps needed for **1,000,000,000** (a billion) sorted entries.

**Answer:** 30 (within ±4)

**Why:** About 30 steps, a billion-entry phone book, solved in the time of 30 comparisons. Logarithms barely grow: **that** is why sorted structures and tree indexes power every database on Earth.

Page: https://tryals.app/practice/physics-i/searching-and-sorting-ideas/binary-search-finds-a-name-among-1-000-sorted-entries-in-10-steps