Searching and sorting
10 flashcards to master Searching and sorting
Smart Spaced Repetition
Rate each card Hard, Okay, or Easy after flipping. Your progress is saved and cards are scheduled for optimal review intervals.
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.
About Searching and sorting (7.2)
These 10 flashcards cover everything you need to know about Searching and sorting for your Cambridge IGCSE Computer Science (0478) exam. Each card is designed based on the official syllabus requirements.
What You'll Learn
- 6 Definitions - Key terms and their precise meanings that examiners expect
- 2 Key Concepts - Core ideas and principles from the 0478 syllabus
How to Study Effectively
Use the Study Mode button above to test yourself one card at a time. Try to answer each question before flipping the card. Review cards you find difficult more frequently.
Continue Learning
After mastering Searching and sorting, explore these related topics:
- 7.1 Algorithm design - 9 flashcards
- 7.3 Testing and validation - 9 flashcards
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