Sorting and Searching Algorithms Flashcards
What are the 3 components of a Bubble sort?
- Outer loop: Loops through the list until no swaps have been made
- Inner loop: Loops through every item in the array
- If-statement: Compares 2 items and swaps if first is greater than second
What is the Big O efficiency of a Bubble sort?
O (n^2)
Why are Bubble sort algorithms inefficient?
They require multiple loops through data that has already been sorted
How does a Binary search work?
- Choose a midpoint and divide data into two halves
- If the key is smaller than the midpoint, delete the right half
- if the key is larger than the midpoint, delete the left half
- repeat until item is found or there are no data items remaining
What is the Big O efficiency of a Binary search?
O (log n)
How does the partition step of a Quicksort work?
- A pivot value is chosen
- If the rightmost value is larger than the pivot, the next item is compared
- If the rightmost value is smaller than the pivot, the two numbers are swapped.
- After a swap, the next item after the swapped item on the side closest to the pivot will be compared
- After all swaps have been completed, the pivot value will never be swapped again as it has been sorted
How does the recursive step of a Quicksort work?
- Repeat the partition step on all items to the left of the pivot
- Repeat the partition step on all items to the right of the pivot
What swaps would occur if a quicksort was used on this set of numbers? Take 15 as the pivot value
15, 32, 4, 7, 89, 12, 69
- 12, 32, 4, 7, 89, 15, 69
- 12, 15, 4, 7, 89, 32, 69
- 12, 7, 4, 15, 32, 69
What is the Big O efficiency of a Quicksort
0 (n log n)
What is the Big O efficiency of a linear search?
O (n)
How does adding a sentinel value to a linear search increase the efficiency?
Guarantees the search item is found, so eliminates the need to check if the end of the list has been reached.
