Virtual Labs

Sorting through Reducing

Consider the array [8, 3, 5, 4, 7, 6, 1, 2]. If we use the first element (8) as pivot in QuickSort, how many elements will be in the left partition after the first partitioning step?

a: 3 Explanation

Explanation

b: 6 Explanation

Explanation

c: 7 Explanation

Explanation

d: 4 Explanation

Explanation

What happens when QuickSort is applied to an already sorted array using the first element as pivot?

a: It runs in O(n log n) time Explanation

Explanation

b: It runs in O(n²) time with maximum recursion depth Explanation

Explanation

c: It runs in O(n) time Explanation

Explanation

d: It fails to sort the array Explanation

Explanation

In the Lomuto partition scheme, if we have array [4, 1, 3, 9, 7] with pivot = 4, what will be the final position of the pivot after partitioning?

a: Index 0 Explanation

Explanation

b: Index 1 Explanation

Explanation

c: Index 2 Explanation

Explanation

d: Index 3 Explanation

Explanation

Which pivot selection strategy provides the best guaranteed performance for QuickSort?

a: Random pivot Explanation

Explanation

b: Median-of-three Explanation

Explanation

c: True median (median-of-medians) Explanation

Explanation

d: First element Explanation

Explanation

In 3-way QuickSort, how are elements partitioned relative to the pivot?

a: Less than pivot, greater than pivot Explanation

Explanation

b: Less than pivot, equal to pivot, greater than pivot Explanation

Explanation

c: Even numbers, odd numbers Explanation

Explanation

d: First half, second half Explanation

Explanation

What is the key advantage of QuickSort over MergeSort?

a: QuickSort is always faster Explanation

Explanation

b: QuickSort is stable Explanation

Explanation

c: QuickSort is in-place with O(log n) space complexity Explanation

Explanation

d: QuickSort handles duplicates better Explanation

Explanation

If QuickSort makes 'n' comparisons in the best case for sorting n elements, what is the recurrence relation?

a: T(n) = 2T(n/2) + O(1) Explanation

Explanation

b: T(n) = 2T(n/2) + O(n) Explanation

Explanation

c: T(n) = T(n-1) + O(n) Explanation

Explanation

d: T(n) = T(n/2) + O(n) Explanation

Explanation

In a hybrid QuickSort implementation, why might it switch to Insertion Sort for small subarrays?

a: Insertion Sort is more accurate Explanation

Explanation

b: To reduce the recursion overhead and improve performance on small arrays Explanation

Explanation

c: Insertion Sort uses less memory Explanation

Explanation

d: To make the algorithm stable Explanation

Explanation

Consider an array with all identical elements. What would be the time complexity of standard QuickSort versus 3-way QuickSort?

a: Both O(n log n) Explanation

Explanation

b: Standard: O(n²), 3-way: O(n) Explanation

Explanation

c: Standard: O(n), 3-way: O(n log n) Explanation

Explanation

d: Standard: O(n log n), 3-way: O(n) Explanation

Explanation

What is the expected number of comparisons made by randomized QuickSort to sort n distinct elements?

a: n log n Explanation

Explanation

b: 1.39 n log n Explanation

Explanation

c: 2n log n Explanation

Explanation

d: n² Explanation

Explanation