Sorting Algorithms (Module 5) PART 2 Flashcards
Which sorting method uses loops to process elements step by step, progressively refining the order of the array?
iterative sorting method
What are the 2 common techniques for iterative sorting methods?
insertion sort and selection sort
Which sorting algorithm builds a sorted portion by inserting each element into the correct position?
insertion sort
Which sorting algorithm repeatedly selects the smallest (or largest) element form the unsorted portion and swaps it with the first unsorted element?
selection sort
Iterative sorting methods usually have a time complexity of O(n^2), making them less efficient for ________.
large datasets
How does the mechanism for insertion sort work? (3 steps)
1) start with empty “sorted’ section
2) take elements from “unsorted” section and insert them into correct position in the sorted section
3) repeat until all elements are sorted
The worst-case time complexity for insertion sorting is when the array is in the ________ order.
reversed
What is the best-case time complexity for selection sorting?
O(n^2)
Is selection sorting a stable sort?
no!
For selection sort, there are at most ________ swaps
n-1
Recursive sorting methods use _____-___-_______ strategy
divide-and-conquer
Recursive sorting methods require ____ space for recursive calls
stack space
What are the 3 steps for the divde-and-conquer strategy
1) Divide (break problem into smaller problems)
2) Conquer (solve smaller problems)
3) Combine the solutions from the smaller problems into the final solution
Quick sort partition the array around a pivot value which yields ____ < _____ < _______
L < pivot < G
What is the mechanism for quick sort? (3 steps)
1) choose P (pivot) and partition L< P and G > P
2) divide-and-conquer L and G
3) merge together
Which pivot consists of randomly selecting a pivot?
random pivot
Which pivot consists of using the first element as a pivot?
first element pivot
Which pivot uses the median as the pivot?
median-of-three pivot
What is the best type of pivot to use, and why?
median-of-three pivot because it takes O(n log n)
