Quick Sort Experiment

1. Quick Sort is generally considered to be:

a: A stable sorting algorithm in every implementation Explanation

Explanation

b: An unstable sorting algorithm in every implementation Explanation

Explanation

c: Stable only when the input array is already sorted Explanation

Explanation

d: Dependent on the implementation; the standard in-place version is generally not stable Explanation

Explanation

2. Given a random policy for choosing the pivot, when can Quick Sort encounter its worst-case time complexity?

a: When most chosen pivots are the smallest elements in their respective subarrays Explanation

Explanation

b: When most chosen pivots are the largest elements in their respective subarrays Explanation

Explanation

c: When most pivots divide their subarrays into two approximately equal parts Explanation

Explanation

d: When either a or b occurs repeatedly Explanation

Explanation

3. Consider the following Quick Sort pseudo-code. Which pair can be selected for blanks (A) and (B) simultaneously so that values smaller than the pivot go to smaller_array and values greater than or equal to the pivot go to bigger_array?

quick_sort(array) -> sorted-array:
    if array is empty: return array
    pivot = choose_pivot_index()
    smaller_array = [], bigger_array = []
    for i = 1 to sizeof(array):
        if (-----A-----):
            append array[i] to smaller_array
        else if (-----B-----):
            append array[i] to bigger_array
    return quick_sort(smaller_array) + [array[pivot]] + quick_sort(bigger_array)

a: array[i] < array[pivot] and array[i] >= array[pivot] Explanation

Explanation

b: array[i] <= array[pivot] and array[i] > array[pivot] Explanation

Explanation

c: array[i] < array[pivot] and array[i] > array[pivot] Explanation

Explanation

d: array[i] <= array[pivot] and array[i] >= array[pivot] Explanation

Explanation

4. What is the average-case time complexity of Quick Sort when pivot selection produces reasonably balanced partitions?

O(n^2)

Explanation

O(n)

Explanation

O(n \log n)

Explanation

O(\log n)

Explanation

5. What is the worst-case time complexity of Quick Sort when every partition places only one element on one side of the pivot and all remaining elements on the other side?

O(n)

Explanation

O(n \log n)

Explanation

O(\log n)

Explanation

O(n^2)

Explanation

6. Which statement best describes the auxiliary space complexity of recursive Quick Sort?

a: It is always

O(1)

regardless of pivot selection. Explanation

Explanation

b: It is typically

O(\log n)

for balanced recursion but can become

O(n)

in the worst case. Explanation

Explanation

c: It is always

O(n^2)

because every partition creates a new array. Explanation

Explanation

d: It is always

O(n)

because Quick Sort stores a complete copy of the input. Explanation

Explanation

7. Which property of Quick Sort is most directly responsible for its average-case time complexity of

O(n \log n)

a: The array is divided into approximately equal subarrays over successive partitioning steps. Explanation

Explanation

b: Every element is compared with every other element exactly once. Explanation

Explanation

c: The algorithm always chooses the smallest element as the pivot. Explanation

Explanation

d: The algorithm performs no comparisons after the first partition. Explanation

Explanation

8. If the pivot divides an array of size

n

into two subarrays of approximately equal size, which recurrence best represents the running time of Quick Sort for that partition pattern?

T(n) = T(n - 1) + O(1)

Explanation

T(n) = 2T(n / 2) + O(n)

Explanation

T(n) = T(n / 2) + O(1)

Explanation

T(n) = 2T(n) + O(n)

Explanation

9. Which comparison of sorting algorithms is correct for their typical time complexities?

a: Quick Sort has

O(n \log n)

average-case time, while Merge Sort has

O(n \log n)

worst-case time. Explanation

Explanation

b: Quick Sort has

O(n)

worst-case time, while Bubble Sort has

O(\log n)

worst-case time. Explanation

Explanation

c: Quick Sort has

O(\log n)

average-case time, while Heap Sort has

O(n)

worst-case time. Explanation

Explanation

d: Quick Sort has

O(n^2)

average-case time, while Merge Sort has

O(n^2)

worst-case time. Explanation

Explanation