Overview
This lecture covers four main algorithms for searching and sorting arrays: linear search, binary search, bubble sort, and selection sort. It explains their logic, example code, exam expectations, and compares their efficiency and use cases.
IB Exam Requirements for Searching & Sorting
- Know how to explain how linear search, binary search, bubble sort, and selection sort work.
- Be able to provide a text-based description of each algorithm.
- Coding these algorithms in IB pseudo code is rare for SL but more common in HL; focus on linear search coding at a minimum.
- Understand that binary search requires a sorted array.
- Be able to compare both searching and both sorting algorithms.
Linear Search
- Linear search checks each element in an array sequentially for the target value.
- Stops when the target is found, outputs its index, or continues to the end if not found.
- Basic pseudo code: loop through the array, compare each element to the target, set a flag when found.
Binary Search
- Binary search works only on sorted arrays.
- Repeatedly divides the array in half, checking if the target is less than, greater than, or equal to the middle element.
- Adjusts the search range (low and high indices) until the target is found or search space is empty.
- Requires tracking of low, high, and mid indices in code.
Comparison: Linear vs Binary Search
- Linear search examines elements one by one; binary search splits the array in half each round.
- Binary search is much faster (O(log n)) but needs a sorted array; linear search is O(n).
- Best case for both: 1 comparison; worst case linear: n comparisons; binary: log₂n comparisons.
- Sorting the array for binary search adds overhead if the array is not already sorted.
Bubble Sort
- Bubble sort compares adjacent elements and swaps if out of order, making multiple passes through the array.
- Each pass moves the largest unsorted value to its correct position at the end.
- Requires nested loops: outer for passes, inner for comparison and swapping.
- May require up to n-1 passes for n elements to be sorted.
Selection Sort
- Selection sort finds the minimum (or maximum) value in the unsorted portion and swaps it with the current position.
- Repeats this process from start to finish, shrinking the unsorted portion each time.
- Uses nested loops: outer for index, inner to find min (or max) in remaining array.
- Only one swap per pass, can be more memory efficient.
Comparison: Bubble Sort vs Selection Sort
- Both use nested loops and progressively reduce the unsorted section.
- Bubble sort repeatedly swaps adjacent out-of-order elements; selection sort only swaps once per pass (minimum with current index).
- Bubble sort can exit early if the array is already sorted; selection sort always scans the unsorted section fully.
Key Terms & Definitions
- Linear Search — Checks each element in sequence until the target is found or array ends.
- Binary Search — Divides a sorted array in half each step to locate the target.
- Bubble Sort — Repeatedly swaps adjacent out-of-order elements through multiple passes.
- Selection Sort — Finds the minimum in the unsorted part and swaps with the starting element of that part.
- Flag — A Boolean variable used to track if the target was found during searching.
Action Items / Next Steps
- Practice writing text-based descriptions and pseudo code for all four algorithms.
- Memorize differences and similarities between both searching and sorting methods.
- Review sample IB exam questions involving searching and sorting algorithms.