Searching and sorting algorithms (AS Level) flashcards

Topic 4: Searching and sorting algorithms

Linear search vs binary search

Linear checks each item in turn from the start; the list can be in any order. Binary repeatedly checks the middle item of an ordered list and discards the half that cannot hold the target.

How do worst-case comparisons grow for linear and binary search?

Linear: in step with the list length. Binary: by just one each time the list length doubles.

How does a bubble sort work?

It repeatedly compares adjacent pairs and swaps any in the wrong order. One sweep through the list is a pass.

What are the two improvements to the basic bubble sort?

Check one fewer item on each pass (the end is already sorted), and stop after a pass with no swaps.

How does merge sort work?

Split the list into single-item lists, then repeatedly merge sorted lists in pairs until one list remains.

Bubble sort vs merge sort: time and memory

Bubble sort is slow on large unsorted lists but sorts in place with one temporary variable and stops early on a nearly sorted list. Merge sort is much faster on large lists but needs extra memory for the sub-lists.

Give the best and worst Big O for linear search, binary search and bubble sort

Linear search O(1) best, O(n) worst. Binary search O(1) best, O(log n) worst. Bubble sort O(n) best, O(n²) worst. Merge sort is O(n log n). (Big O is International A-level only.)

Definite vs indefinite iteration

Definite iteration runs a fixed number of times (FOR). Indefinite iteration runs until a condition is met (WHILE).