Searching and sorting
Cambridge IGCSE Computer Science (0478) · Unit 7: Algorithm design and problem solving · 10 flashcards
Searching and sorting is topic 7.2 in the Cambridge IGCSE Computer Science (0478) syllabus , positioned in Unit 7 — Algorithm design and problem solving , alongside Algorithm design and Testing and validation. In one line: Linear search sequentially checks each element in a list until the target is found or the end is reached. In the worst case (target is last or not present), it has a time complexity of O(n), where n is the number of elements.
This topic is examined in Paper 1 (computer systems theory) and Paper 2 (algorithms, programming and logic).
The deck below contains 10 flashcards — 6 definitions, 2 key concepts and 1 application card — covering the precise wording mark schemes reward. Use the 6 definition cards to lock down command-word answers (define, state), then move on to the concept and application cards to handle explain, describe and compare questions.
Describe the linear search algorithm and state its time complexity in the worst-case scenario
Linear search sequentially checks each element in a list until the target is found or the end is reached. In the worst case (target is last or not present), it has a time complexity of O(n), where n is the number of elements.
Questions this Searching and sorting deck will help you answer
- › Compare the efficiency of linear search and binary search in a sorted array.
- › Describe a situation where using a linear search would be more appropriate than a binary search.
- › Compare the efficiency of bubble sort and merge sort.
Describe the linear search algorithm and state its time complexity in the worst-case scenario.
Linear search sequentially checks each element in a list until the target is found or the end is reached. In the worst case (target is last or not present), it has a time complexity of O(n), where n is the number of elements.
Explain how the binary search algorithm works and state its pre-requisite for usage.
Binary search repeatedly divides the search interval in half. If the middle element matches the target, the search ends. Otherwise, the search continues in either the left or right half, depending on the target's value compared to the middle element. It requires a sorted list.
Outline the steps involved in the bubble sort algorithm.
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element 'bubbles' to the end with each pass. This process is repeated until no more swaps are needed.
Describe the key principle behind the merge sort algorithm.
Merge sort is a divide-and-conquer algorithm. It recursively divides the list into smaller sublists, sorts each sublist, and then merges the sorted sublists back together to produce the final sorted list.
Explain how the insertion sort algorithm works.
Insertion sort builds the final sorted array one item at a time. It iterates through the input data, removes one element at each repetition, finds the location where that element belongs within the sorted array, and inserts it there.
Compare the efficiency of linear search and binary search in a sorted array.
Binary search (O(log n)) is significantly more efficient than linear search (O(n)) for sorted arrays, especially for large datasets. Linear search must check every element in the worst case, while binary search quickly narrows the search range.
Describe a situation where using a linear search would be more appropriate than a binary search.
Linear search is more appropriate when the dataset is small or unsorted. The overhead of sorting the data to use binary search might outweigh the benefits for small datasets.
Explain the concept of 'comparison' in the context of sorting algorithms.
Comparison refers to the operation of checking whether one element is greater than, less than, or equal to another element. Sorting algorithms like bubble sort, merge sort, and insertion sort use comparisons to determine the correct order of elements.
Compare the efficiency of bubble sort and merge sort.
Merge sort (O(n log n)) is significantly more efficient than bubble sort (O(n^2)) for larger datasets. Bubble sort's performance degrades rapidly as the input size increases, while merge sort scales much better.
If a list of 1024 items is to be sorted using binary search, what is the maximum number of comparisons to find if an item exists?
A binary search will take a maximum of 11 comparisons, since log base 2 of 1024 is 10. 2^10 = 1024. The question asks for the *number of comparisons*, not the number of splits.
Key Questions: Searching and sorting
Describe the linear search algorithm and state its time complexity in the worst-case scenario.
Linear search sequentially checks each element in a list until the target is found or the end is reached. In the worst case (target is last or not present), it has a time complexity of O(n), where n is the number of elements.
Explain how the binary search algorithm works and state its pre-requisite for usage.
Binary search repeatedly divides the search interval in half. If the middle element matches the target, the search ends. Otherwise, the search continues in either the left or right half, depending on the target's value compared to the middle element. It requires a sorted list.
Outline the steps involved in the bubble sort algorithm.
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element 'bubbles' to the end with each pass. This process is repeated until no more swaps are needed.
Describe the key principle behind the merge sort algorithm.
Merge sort is a divide-and-conquer algorithm. It recursively divides the list into smaller sublists, sorts each sublist, and then merges the sorted sublists back together to produce the final sorted list.
Explain how the insertion sort algorithm works.
Insertion sort builds the final sorted array one item at a time. It iterates through the input data, removes one element at each repetition, finds the location where that element belongs within the sorted array, and inserts it there.
More topics in Unit 7 — Algorithm design and problem solving
Searching and sorting sits alongside these Computer Science decks in the same syllabus unit. Each uses the same spaced-repetition system, so progress in one informs the next.
Cambridge syllabus keywords to use in your answers
These are the official Cambridge 0478 terms tagged to this section. Mark schemes credit responses that use the exact term — weave them into your answers verbatim rather than paraphrasing.
Key terms covered in this Searching and sorting deck
Every term below is defined in the flashcards above. Use the list as a quick recall test before your exam — if you can't define one of these in your own words, flip back to that card.
How to study this Searching and sorting deck
Start in Study Mode, attempt each card before flipping, then rate Hard, Okay or Easy. Cards you rate Hard come back within a day; cards you rate Easy push out to weeks. Your progress is saved in your browser, so come back daily for 5–10 minute reviews until every card reads Mastered.
Study Mode
Space to flip • ←→ to navigate • Esc to close
You're on a roll!
You've viewed 10 topics today
Create a free account to unlock unlimited access to all revision notes, flashcards, and study materials.
You're all set!
Enjoy unlimited access to all study materials.
Something went wrong. Please try again.
What you'll get:
- Unlimited revision notes & flashcards
- Track your study progress
- No spam, just study updates