quicksort Flashcards
(20 cards)
What is the main idea behind Treesort?
Insert elements into a BST, then return the inorder traversal.
Why does inorder traversal of a BST return a sorted list?
Because in a BST, left < node < right is always true.
What is the worst-case complexity of Treesort?
O(n²), if the BST becomes unbalanced.
How can we ensure Treesort runs in O(n log n) time?
Use a self-balancing tree like an AVL tree.
What is stability in sorting?
Maintaining the relative order of elements with equal keys.
Is BST-based Treesort stable by default?
No, because equal elements may be inserted in arbitrary order.
How can stability be preserved in a tree-based sort?
By consistently placing duplicates to the right or tagging entries with input order.
What is Big-O notation used for?
Describing an upper bound on algorithm growth — worst-case performance.
What is Big-Theta notation used for?
Describing the tight bound — the actual growth rate.
Why is it important to use Big-O and Big-Theta properly?
To avoid misrepresenting algorithm efficiency and complexity.
What is Quicksort inspired by?
The idea of constructing a BST and performing an inorder traversal — but done in-place.
How does Quicksort work?
It partitions the array around a pivot, then recursively sorts the subarrays.
What is the role of the pivot in Quicksort?
It divides the array into elements smaller and greater than itself.
What is Quicksort’s average-case complexity?
O(n log n)
What is Quicksort’s worst-case complexity?
O(n²), usually when the pivot is poorly chosen.
How can we avoid Quicksort’s worst-case performance?
By shuffling the input or using better pivot selection methods.
Why is Quicksort faster than mergesort in practice?
Because it uses less memory and benefits from better cache usage.
What is a practical optimization used in Quicksort?
Switching to insertion sort for small subarrays — a polyalgorithm.
What is a median-of-three strategy?
A pivot selection heuristic that picks the median of the first, middle, and last elements.
Why is Quicksort not stable by default?
Because swaps can move equal elements out of their original order.
