Chapter 2 Sorting Flashcards

(29 cards)

1
Q

What is the goal of sorting?

A

To arrange elements in non-decreasing order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does BruteSort do?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the time complexity of BruteSort?

A

O(n!)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Why is BruteSort inefficient?

A

It checks every permutation, which grows factorially with n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is InsertionSort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the time complexity of InsertionSort?

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the principle behind MergeSort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the time complexity of MergeSort?

A

O(n log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does Merge do in MergeSort?

A

Combines two sorted arrays into one sorted array.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is QuickSort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the worst-case complexity of QuickSort?

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is RandomisedQuickSort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Expected complexity of RandomisedQuickSort?

A

O(n log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is BucketSort?

A

Sorts by placing values into buckets and sorting each bucket.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

When is BucketSort efficient?

A

When the data is uniformly distributed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the worst-case complexity of BucketSort?

17
Q

What is the selection problem?

A

Finding the i-th smallest element in an array.

18
Q

What is RandomisedSelect?

A

A QuickSort-based algorithm to find order statistics.

19
Q

Expected complexity of RandomisedSelect?

20
Q

Worst-case complexity of RandomisedSelect?

21
Q

Why is RandomisedPartition used?

A

To reduce the chance of poor pivot selection.

22
Q

What does the partition function do?

A

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

23
Q

What is an order statistic?

A

The i-th smallest element in a sample.

24
Q

Why sort to find order statistics is inefficient?

A

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

25
What is a pivot in QuickSort?
An element used to divide the array into two partitions.
26
What is PlainBucketSort (idea behind it) and its time complexity
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.
27
Explain what a Bucket sort is (explain the pseudocode)?
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.
28
What would happen if the inputs for a bucket sort aren't uniform?
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.
29
What should you do if the inputs of a bucket sort is NOT uniform?
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.