VCE Applied Computing: Software Development (Year 12) · Unit 3 — Programming · 18m read

Searching and Sorting — Linear and Binary Search, Selection Sort and Quick Sort

Searching and sorting algorithms are the classic Software Development exam items. You will be asked to trace them by hand, count steps, and justify which is more efficient for a given situation.

Learning objective: Trace and compare linear and binary search and selection sort and quick sort, and explain their efficiency for different data sizes.

By the end of this lesson you can:

• I can trace linear and binary searches and count comparisons.
• I can trace selection sort and the partition step of quick sort.
• I can compare algorithms by efficiency and explain when each is suitable.

Binary search is finding a word in a dictionary. You do not start at "a" and read every word — you open the middle, decide which half, and repeat. That only works because the dictionary is sorted.

Searching

LINEAR SEARCH — check each element in turn until the target is found or the list ends.
• Works on unsorted data.
• Worst case: n comparisons for n items.

BINARY SEARCH — on a SORTED list, compare the target with the middle element; discard the half that cannot contain it; repeat.
• Worst case: about log₂ n comparisons (1 000 000 items → about 20 comparisons).
• Requires the data to be sorted first.

FUNCTION binarySearch(list, target)
low ← 0
high ← LENGTH(list) − 1
WHILE low ≤ high
mid ← (low + high) DIV 2
IF list[mid] = target THEN RETURN mid
ELSE IF list[mid] < target THEN low ← mid + 1
ELSE high ← mid − 1
ENDIF
ENDWHILE
RETURN −1
ENDFUNCTION

Sorting

SELECTION SORT — repeatedly find the smallest remaining element and swap it into the next position.
• Simple to code and trace; always about n²/2 comparisons, so slow for large lists.

QUICK SORT — choose a PIVOT, PARTITION the list into elements less than the pivot and elements greater than it, then recursively sort each part.
• Average performance about n log n — much faster than selection sort for large data.
• Worst case (poor pivots, e.g. already-sorted data with the first element as pivot) approaches n².
• Uses recursion: a function that calls itself on smaller sub-lists until each has 0 or 1 elements.

Worked example (Medium)

Trace a binary search for 41 in [3, 8, 15, 23, 41, 56, 72].

1. Pass 1. low = 0, high = 6, mid = 3 → list[3] = 23 < 41, so low = 4.
2. Pass 2. low = 4, high = 6, mid = 5 → list[5] = 56 > 41, so high = 4.
3. Pass 3. low = 4, high = 4, mid = 4 → list[4] = 41. Found.

Answer: Found at index 4 after 3 comparisons (a linear search would need 5).

Worked example (Medium)

Show the list after each pass of selection sort on [29, 10, 14, 37, 13].

1. Pass 1. Smallest is 10; swap with 29. [10, 29, 14, 37, 13]
2. Pass 2. Smallest of the rest is 13; swap with 29. [10, 13, 14, 37, 29]
3. Pass 3. 14 is already in place. [10, 13, 14, 37, 29]
4. Pass 4. Swap 29 and 37. [10, 13, 14, 29, 37]

Answer: [10, 13, 14, 29, 37]

Common mistakes

• Applying binary search to unsorted data Discarding half the list only works if order is guaranteed. Fix: State that the data must be sorted first.
• Saying quick sort is always fastest Its worst case is as slow as selection sort. Fix: Say "on average" and mention pivot choice.
• Forgetting to update low/high to mid ± 1 Setting low = mid can cause an infinite loop. Fix: Exclude the middle element once checked.

Practice questions

1. About how many comparisons does a binary search need in the worst case for 1024 sorted items?

   1. 10
   2. 32
   3. 512
   4. 1024

   (1 marks)

2. A list of 50 unsorted names is searched once. Should the programmer sort it and use binary search, or use linear search? Justify.

   (2 marks)

3. Partition [7, 2, 9, 4, 8] using 7 as the pivot.

   (2 marks)

Summary

• Linear search: any order, up to n comparisons. Binary search: sorted data, about log₂ n comparisons.
• Selection sort: simple, about n²/2 comparisons.
• Quick sort: pivot + partition + recursion, about n log n on average.
• Choose algorithms by data size, whether data is sorted and how often it is searched.