SDD - Standard Algorithms Flashcards
What are the three main differences between a Binary Search and a Linear Search?
- A Binary search requires a sorted list, while a Linear search doesn’t
- Linear checks every single value in the list, whereas Binary constantly halves the list until it finds the value
- Binary searches work well on long lists, while Linear searches work well on short lists
Explain what a Selection sort is…
A Selection sort uses two lists, the unsorted list and an empty list. The sort finds the minimum value in the list, and puts it in the first spot in the empty list, it then replaces that minimum with a dummy value, so it can’t be chosen again. It repeats this process until all the values have been sorted into the new list.
Explain how a Bubble sort searches…
A Bubble sort compares one value worth the next value and if the first value is greater they switch places. This process repeats until the maximum value has ‘bubbled’ to the end. This repeats but finishes at the second last place in the list. It continues this process until the list has been sorted.
How does the Insertion sort work?
What sorts would be most suitable for a parallel processing solution?
The Quick sort or the Merge sort
Which sort uses two lists?
The Selection sort
How does a Binary search work?
It continuously divides the list in half, and repeats the process on the sub list most likely to contain the search value, this repeats until the value is found or the lower index is greater than upper.
What does the efficiency of a sort depend on?
How many comparisons and swaps it will make, whether the require additional memory and whether the sort can realise if the list is already sorted half way through the sort.
