Sorting Algorithms Flashcards
Which sorting algorithm only sorts if the array is not already sorted?
Insertion Sort
Why is it called “insertion sort”
Each pass through the array takes the first element that is out of place and inserts it into its proper place
Which sorting algorithm uses two loops?
Bubble sort
Which sorting algorithm will have the largest element in it’s proper position after one pass?
Bubble sort
What is the “key” in a selection sort?
The smallest entry
How does selection sort work?
Find the smallest value and replace with lowest element available.
Which sorting algorithm compares 2 adjacent elements on each pass?
Bubble sort
How is information about a function call stored?
Dynamically using the runtime stack
What information is saved with a function call?
Parameters, variables, and return address
What is the data about a function call named?
Activation Record
What’s another word for activation record?
Stack Frame
What is the anchor in recursion?
The last recursive call
What does the anchor do in a recursive call?
Ensures we don’t fall into an infinite loop
What are the three types of recursion?
1) Linear
2) Binary
3) Multiple
Which two algorithms are based on a divide and conquer approach?
Merge Sort and Quick Sort
