Searching and Sorting Algorithms (OCR A-Level Computer Science): Flashcards

Locate specific data within a collection

Arrange data in specific order (ascending/descending)

None - works on sorted & unsorted data

Data must be sorted in ascending or descending order

$O(n)$

$O(\log n)$

Searches each element sequentially

Repeatedly divides search interval in half

Repeatedly swaps adjacent elements if in wrong order

$O(n^2)$

Builds sorted list one item at a time

$O(n \log n)$

Divides array into halves, sorts each, then merges

$O(n^2)$ - due to poor pivot selection

Partitions array around pivot, recursively sorts partitions