Chapter 2 Sorting

Question 1

What is the goal of sorting?

Answer 1

To arrange elements in non-decreasing order.

Question 2

What does BruteSort do?

Answer 2

Tries all permutations of the array until it finds a sorted one.

Question 3

What is the time complexity of BruteSort?

Answer 3

O(n!)

Question 4

Why is BruteSort inefficient?

Answer 4

It checks every permutation, which grows factorially with n.

Question 5

What is InsertionSort?

Answer 5

A sorting algorithm that inserts elements into their correct position in a growing sorted portion.

Question 6

What is the time complexity of InsertionSort?

Answer 6

O(n^2)

Question 7

What is the principle behind MergeSort?

Answer 7

Divide-and-conquer: divide the array, sort each half, merge them.

Question 8

What is the time complexity of MergeSort?

Answer 8

O(n log n)

Question 9

What does Merge do in MergeSort?

Answer 9

Combines two sorted arrays into one sorted array.

Question 10

What is QuickSort?

Answer 10

A divide-and-conquer sorting algorithm using a pivot to partition the array.

Question 11

What is the worst-case complexity of QuickSort?

Answer 11

O(n^2)

Question 12

What is RandomisedQuickSort?

Answer 12

QuickSort with a random pivot to reduce likelihood of worst-case.

Question 13

Expected complexity of RandomisedQuickSort?

Answer 13

O(n log n)

Question 14

What is BucketSort?

Answer 14

Sorts by placing values into buckets and sorting each bucket.

Question 15

When is BucketSort efficient?

Answer 15

When the data is uniformly distributed.

Question 16

What is the worst-case complexity of BucketSort?

Answer 16

O(n^2)

Question 17

What is the selection problem?

Answer 17

Finding the i-th smallest element in an array.

Question 18

What is RandomisedSelect?

Answer 18

A QuickSort-based algorithm to find order statistics.

Question 19

Expected complexity of RandomisedSelect?

Answer 19

O(n)

Question 20

Worst-case complexity of RandomisedSelect?

Answer 20

O(n^2)

Question 21

Why is RandomisedPartition used?

Answer 21

To reduce the chance of poor pivot selection.

Question 22

What does the partition function do?

Answer 22

Reorders array so elements ≤ pivot are on the left, others on the right.

Question 23

What is an order statistic?

Answer 23

The i-th smallest element in a sample.

Question 24

Why sort to find order statistics is inefficient?

Answer 24

Sorting takes O(n log n), but selection can be done in O(n).

Question 25

What is a pivot in QuickSort?

Answer 25

An element used to divide the array into two partitions.

Question 26

What is PlainBucketSort (idea behind it) and its time complexity

Answer 26

PlainBucketSort is a linear-time sorting algorithm that works when the input array contains non-repeated integers within a known range from 1 to m. It uses an auxiliary array, z, of size m to record the presence of each number: initially, all entries in z are set to 0. The algorithm then marks the presence of each number in the input array x by setting z[x[i]] = 1. After this marking phase, it scans through z in order from 1 to m and builds the sorted output array y by including each number i for which z[i] == 1. Since the elements are unique and fall within a bounded range, this method ensures that the output array y is sorted. The total time complexity is O(n+m), making it highly efficient when m is not much larger than n.

Question 27

Explain what a Bucket sort is (explain the pseudocode)?

Answer 27

BucketSort is a sorting algorithm designed for efficiently sorting real numbers that lie within the interval [0, 1). The idea is to divide this interval into m equal-sized subintervals, or "buckets," and distribute the input numbers into these buckets based on their value. Each number x[i] is placed into bucket b[⌊m × x[i]⌋ + 1], which ensures numbers are grouped with others close in value. After all elements are distributed, each bucket is sorted individually using Insertion Sort, which is fast on small or nearly sorted datasets. Finally, the algorithm concatenates all the sorted buckets to produce the sorted array. When the input is uniformly distributed, BucketSort achieves a time complexity of O(n), making it extremely efficient under the right conditions.

Question 28

What would happen if the inputs for a bucket sort aren't uniform?

Answer 28

If the input isn't from a Uniform(0,1) distribution — say it’s skewed, clustered, or from a normal distribution — some buckets may be overloaded and others may be empty. This breaks the balance of the algorithm and leads to performance degradation, potentially up to O(n²) in the worst case.

Question 29

What should you do if the inputs of a bucket sort is NOT uniform?

Answer 29

If your input data isn't uniformly distributed in [0,1), BucketSort can perform poorly because the elements won’t be evenly spread across buckets. To fix this, you can transform each input value x using its cumulative distribution function (CDF) 𝐹𝑋(𝑥)F X(x). This transformation — z=𝐹𝑋(𝑥)z=F X(x) — maps the data to a Uniform(0, 1) distribution. After transforming the data, you can safely apply BucketSort as intended. This approach ensures the algorithm remains efficient, even when the original data isn't uniformly distributed.