Chapter 2 Sorting Flashcards
(25 cards)
What is the goal of sorting?
To arrange elements in non-decreasing order.
What does BruteSort do?
Tries all permutations of the array until it finds a sorted one.
What is the time complexity of BruteSort?
O(n!)
Why is BruteSort inefficient?
It checks every permutation, which grows factorially with n.
What is InsertionSort?
A sorting algorithm that inserts elements into their correct position in a growing sorted portion.
What is the time complexity of InsertionSort?
O(n^2)
What is the principle behind MergeSort?
Divide-and-conquer: divide the array, sort each half, merge them.
What is the time complexity of MergeSort?
O(n log n)
What does Merge do in MergeSort?
Combines two sorted arrays into one sorted array.
What is QuickSort?
A divide-and-conquer sorting algorithm using a pivot to partition the array.
What is the worst-case complexity of QuickSort?
O(n^2)
What is RandomisedQuickSort?
QuickSort with a random pivot to reduce likelihood of worst-case.
Expected complexity of RandomisedQuickSort?
O(n log n)
What is BucketSort?
Sorts by placing values into buckets and sorting each bucket.
When is BucketSort efficient?
When the data is uniformly distributed.
What is the worst-case complexity of BucketSort?
O(n^2)
What is the selection problem?
Finding the i-th smallest element in an array.
What is RandomisedSelect?
A QuickSort-based algorithm to find order statistics.
Expected complexity of RandomisedSelect?
O(n)
Worst-case complexity of RandomisedSelect?
O(n^2)
Why is RandomisedPartition used?
To reduce the chance of poor pivot selection.
What does the partition function do?
Reorders array so elements ≤ pivot are on the left, others on the right.
What is an order statistic?
The i-th smallest element in a sample.
Why sort to find order statistics is inefficient?
Sorting takes O(n log n), but selection can be done in O(n).
