Algorithms and Recursion Flashcards
What is the grandfather of all sorting algorithms?
Bubble Sort
What is involved in a bubble sort?
Compare adjacent elements, if the one on the left is larger swap to the right and continue
After one complete pass with a bubble sort algorithm, what will always be true?
The largest value will be in the last element.
How many comparisons are made on each pass of a bubble sort?
array.length - 1
What must your loop continuation condition be in a bubble sort?
i < array.length - 1
What is a major downside of the bubble sort?
Because it compares (n-1) elements each pass, and does (n-1) passes, even if the array was already sorted it still needs to compare (n-1)^2 times.
How many comparisons are done in a bubble sort? (passes and individual included)
(array.length - 1) * (array.length - 1)
What is the LCC for an enhanced bubble sort?
i < array.length - (h + 1); Where h is the counter of the outer loop
How does a “short-circuit” work?
Track number of swaps done with a counter, if zero then use a break statement.
How does a selection sort work?
Find the smallest value in an array and swap with the left-most element
What kind of search algorithm just starts at element 0 and compares every element?
Linear search
To use a binary search algorithm, what must first be done?
Sort the array
How does the binary search algorithm work?
Look at middle element and compare with value wanted. If value is larger, repeat process to the right. If smaller, to the left until value found.
What is it called when a method calls itself?
Recursion
What is an example of a problem best solved using recursion?
Traversal of a binary tree
