Searching, sorting, hashing

Linear search

Definition. Linear search checks elements one by one until the key is found or the input ends. It works on sorted and unsorted sequences. With n elements, the worst case makes n comparisons; a successful search may stop earlier.

Example. Searching 12 in [4,12,8] uses two comparisons.

Exam point. A missing key requires n comparisons.

Solved trace. Search for 15 in [3,7,11,15,19].

1. Compare with 3: not equal.
2. Compare with 7: not equal.
3. Compare with 11: not equal.
4. Compare with 15: match. Answer. Found at index 3 after four comparisons.

Binary search

Definition. Binary search repeatedly compares the target with the middle item of a sorted array and discards the half that cannot contain the target. It requires a sorted sequence and a consistent interval convention. Its time is O(log n) and iterative auxiliary space is O(1); a recursive version uses O(log n) stack space.

Example. Searching 9 in [1,4,7,9,12] compares the middle and then narrows the interval.

Exam point. Maintain low and high bounds carefully; an off-by-one error can skip the last candidate.

Solved trace. Search for 18 in [2,5,9,13,18,21,27] using inclusive low/high and floor midpoint.

1. low=0, high=6, mid=3; value 13. Since 18>13, set low=4.
2. low=4, high=6, mid=5; value 21. Since 18<21, set high=4.
3. low=4, high=4, mid=4; value 18. Match. Answer. Index 4 after three comparisons.

Comparison sorting and lower bound

Definition. A comparison sort learns key order only by comparing pairs. Any comparison decision tree that sorts n distinct keys needs at least $\lceil\log_2(n!)\rceil=\Omega(n\log n)$ comparisons in the worst case. This bound applies to comparison-based sorting, not to algorithms that exploit restricted key domains.

Example. Sorting 8 distinct values requires at least $\lceil\log_2(8!)\rceil=16$ comparisons in the worst-case decision-tree model.

Exam point. Linear-time counting or radix sorting does not contradict the comparison lower bound.

Insertion sort

Definition. Insertion sort grows a sorted prefix by inserting each next element into its proper position within that prefix. It is in-place and stable when equal elements are not shifted past one another. Its worst-case time is O(n²), while an already sorted input needs O(n) comparisons.

Example. Inserting 4 into sorted prefix [2,5,7] gives [2,4,5,7].

Exam point. The algorithm is adaptive: nearly sorted inputs can be much faster than reverse order.

Solved trace. Sort [5,2,4,1] by insertion sort; show the array after each pass.

1. Insert 2 into [5]: [2,5,4,1].
2. Insert 4 into [2,5]: shift 5 right → [2,4,5,1].
3. Insert 1 into [2,4,5]: shift all three right → [1,2,4,5]. Answer. Sorted array [1,2,4,5]. Comparisons are 1+2+3=6 in this trace.

Selection sort

Definition. Selection sort repeatedly finds the minimum of the unsorted suffix and swaps it into the first suffix position. It makes $n(n-1)/2$ comparisons regardless of input order and uses O(1) auxiliary storage. The usual swap version is not stable.

Example. [6,3,5] selects 3 and swaps to obtain [3,6,5].

Exam point. Count comparisons separately from swaps; comparisons remain quadratic.

Solved trace. Sort [4,1,3,2].

1. Suffix minimum is 1; swap with first: [1,4,3,2].
2. Suffix [4,3,2] minimum is 2; swap: [1,2,3,4].
3. Suffix [3,4] minimum is 3; no effective swap.
4. Comparisons: 3+2+1=6. Answer. [1,2,3,4] after six comparisons.

Bubble sort

Definition. Bubble sort compares adjacent items and swaps out-of-order pairs. A left-to-right pass moves a maximum toward the right end. With an early-stop flag, sorted input takes O(n) time; worst-case time is O(n²). It is stable if equal items are not swapped.

Example. One pass over [3,1,4] gives [1,3,4].

Exam point. Identify the pass direction to determine which extreme reaches its final position.

Solved trace. Perform one left-to-right pass on [4,2,5,1].

1. Compare 4,2: swap → [2,4,5,1].
2. Compare 4,5: no swap.
3. Compare 5,1: swap → [2,4,1,5]. Answer. One pass gives [2,4,1,5]; maximum 5 is fixed at the end.

Merge sort

Definition. Merge sort divides an array into halves, recursively sorts each half, and merges the sorted halves. Its worst-case time is O(n log n), and an array implementation typically uses O(n) auxiliary space. Standard merging is stable when equal keys are taken from the left half first.

Example. Merge [2,6] and [1,5] by repeatedly selecting the smaller front item.

Exam point. The merge step costs linear time in the total subarray length.

Solved trace. Sort [8,3,6,2] using merge sort.

1. Split into [8,3] and [6,2].
2. Sort left: split [8],[3], then merge to [3,8].
3. Sort right: split [6],[2], then merge to [2,6].
4. Merge [3,8] and [2,6]: take 2, then 3, then 6, then 8. Answer. [2,3,6,8].

Quicksort and partitioning

Definition. Quicksort partitions items around a pivot, recursively sorts the regions, and combines them without a separate merge. A balanced partition gives O(n log n) time; repeatedly extreme partitions give O(n²) worst-case time. In-place partitioning can use O(log n) expected recursion stack for balanced splits, but worst-case depth can be O(n).

Example. Partitioning [4,1,6,3] around pivot 3 places smaller keys on one side and larger keys on the other.

Exam point. Partition details determine which side receives keys equal to the pivot.

Solved trace. Use Lomuto partition on [6,2,7,3,5] with last item 5 as pivot; use <= pivot for the left partition.

1. Start boundary i=-1.
2. 6>5: no change.
3. 2≤5: increment i=0 and swap positions 0 and 1, giving [2,6,7,3,5].
4. 7>5: no change.
5. 3≤5: increment i=1, swap positions 1 and 3 → [2,3,7,6,5].
6. Place pivot at i+1=2 by swapping with 5 → [2,3,5,6,7]. Answer. Pivot 5 ends at index 2; left partition [2,3], right [6,7].

Heap sort

Definition. Heapsort builds a max-heap, repeatedly exchanges the root with the last item in the active heap, shrinks the heap, and restores heap order. It runs in O(n log n) worst-case time and can sort in-place with O(1) auxiliary array space. It is not stable in the usual implementation.

Example. The maximum at the heap root is placed at the final active index.

Exam point. Exclude the sorted suffix from subsequent heap operations.

Solved trace. One heapsort extraction from max-heap [9,7,8,2,5].

1. Swap 9 with the last active key 5: [5,7,8,2,9].
2. Shrink active size to 4.
3. Compare children 7 and 8; swap root 5 with larger child 8: [8,7,5,2,9].
4. At index 2, 5 has no active child. Answer. Active heap [8,7,5,2], sorted suffix [9].

Counting sort

Definition. Counting sort counts occurrences of keys in a known integer range and uses cumulative counts to determine output positions. It runs in O(n+k) time and uses O(n+k) space for n items and range size k. It is stable when output placement processes input in reverse using cumulative counts.

Example. For keys 0,2,2, the frequency array is [1,0,2].