Computational Thinking, Searching & Sorting Algorithms Flashcards
Card 1 of 28
All 28 cards in this deck
What are the three principles of computational thinking?
Abstraction, decomposition and algorithmic thinking.
What is abstraction?
Removing or ignoring unnecessary detail from a problem so only the key features needed to solve it remain.
What is decomposition?
Breaking a problem down into smaller sub-problems that are easier to solve.
e.g. a quiz program splits into: store questions, ask questions, check answers, keep score.What is algorithmic thinking?
Working out the sequence of steps needed to solve a problem, so the solution can be written as an algorithm.
In a route-planning app, give one detail abstraction keeps and one it removes.
Keeps: roads and distances between places. Removes: colours of buildings, names of shops, scenery.
True or false? Abstraction means breaking a problem into smaller sub-problems.
False. That is decomposition; abstraction is removing unnecessary detail.
What are the main steps of a linear search?
e.g. search 4, 9, 2, 7 for the value 2- Compare the first value to the value searched for: .
- If they match, stop — the item is found.
- If not, move to the next value and repeat: , then → found.
What are the main steps of a binary search?
e.g. find 10 in 1, 2, 5, 6, 7, 10, 20- Pick out the middle value: 6.
- If it is not the value searched for, discard the half it cannot be in: , so discard 1, 2, 5, 6 and keep 7, 10, 20.
- Repeat on the remaining list: middle value is 10 → found.
State one pre-requisite for a binary search.
The data must be sorted / in order.
True or false? A linear search can only be used on data that is in order.
False. A linear search works on unsorted data; only a binary search needs sorted data.
Other than finding the value, what condition stops a linear search?
The end of the list is reached / every value has been checked (and the value was not found).
Which search would you choose for a large list that is already sorted, and why?
Binary search — it halves the list each time, so it needs far fewer comparisons than a linear search.
What are the main steps of a bubble sort?
e.g. sort 3, 1, 2- Compare the first pair and swap them if they are in the wrong order: 1, 3, 2.
- Move along one place and repeat to the end of the list (one pass): 1, 2, 3.
- Repeat passes until a pass makes no swaps: list is sorted as 1, 2, 3.
What are the main steps of an insertion sort?
e.g. sort 5, 2, 4- Treat the first item as the sorted part and take the next item: 2.
- Compare it back through the sorted part and insert it in the correct place: 2, 5.
- Repeat for every remaining item: insert 4 → 2, 4, 5.
What are the main steps of a merge sort?
e.g. sort 4, 1, 3, 2- Split the list in half repeatedly until each list holds one item: 4 | 1 | 3 | 2.
- Merge pairs of lists, comparing values so each merged list is in order: 1, 4 and 2, 3.
- Keep merging until one list remains: 1, 2, 3, 4.
Which sorting algorithm splits the data into individual items before recombining them in order?
Merge sort.
Which sorting algorithm uses an array with a sorted part and an unsorted part?
Insertion sort.
True or false? A bubble sort always swaps the pair of values it compares.
False. It swaps them only if they are in the wrong order.
True or false? Each comparison in a binary search discards about half of the remaining items.
True. The middle item is compared, then one half of the list is discarded, which makes it faster than a linear search on large sorted lists.
What is an algorithm?
A precise sequence of steps that solves a problem or carries out a task.
Give two advantages of a merge sort over a bubble sort or an insertion sort.
It is much faster on large lists, and its running time stays about the same however the items were ordered to begin with.
Why does a bubble sort or an insertion sort need less memory than a merge sort?
They rearrange the items within the original list, whereas a merge sort creates extra sub-lists as it splits and merges.
Which is quicker at checking that a list is already in order: a bubble sort or a merge sort?
A bubble sort. It makes one pass, finds no swaps and stops, whereas a merge sort still splits and merges every item.
Why is a merge sort efficient?
Very short lists are trivial to sort, and combining two lists that are already in order takes few comparisons.
In a bubble sort into ascending order, where does the largest value end up after the first pass?
At the end of the list, in its final position, so each later pass can stop one item sooner.
In a binary search, which item is the middle one when the list has an even number of items?
There are two central items and either can be used, e.g. item 4 or item 5 of 8. One common rule is position , rounded up.
Give one drawback of a linear search.
It is slow on large lists, because in the worst case every item has to be checked.
Apart from not needing the list to be sorted, give one advantage of a linear search over a binary search.
It is simpler to write and understand.