Quick Sort Quiz

What is the basic idea behind QuickSort?

• • Sorting elements using loops.

• Dividing the array into two parts and sorting independently.

• Selecting the smallest element as the pivot.

• Combining elements randomly

Answer explanation

The basic idea behind QuickSort is dividing the array into two parts and sorting independently.

Explain the process of partitioning in quick sort.

• Randomly shuffling the array elements

• Sorting the array in descending order

• Selecting the middle element as the pivot without rearranging the array

• Rearranging the array so that all elements less than the pivot are on one side and all elements greater than the pivot are on the other side

Answer explanation

What is the time complexity of quick sort in the best case?

• O(1)

• O(n log n)

• O(n^2)

• O(n)

Why is QuickSort considered cache-friendly?

• It uses additional storage space.

• • It doesn’t need additional storage space.

• It only works in virtual memory.

• It doesn't consider cache.

How many comparisons are made before the array is put into an order in quick sort?

• 1 comparison

• 100 comparisons

• 10 comparisons

• It varies

What are the different methods for pivot selection in quick sort?

• Randomly picking a pivot

• Only one method available

• Always selecting the smallest element as pivot

• All of the above

What is the worst-case time complexity of quick sort.

• O(1)

• O(n^2)

• O(n log n)

• O(n!)

Explain the concept of pivot element in quick sort.

• The pivot element is the smallest element in the array.

• The pivot element is the largest element in the array.

• The pivot element is randomly selected from the array.

• The pivot element is the element around which the array is partitioned in quick sort.

What is the role of recursion in quick sort?

• Recursion is not used in quick sort

• Recursion is only used for merging the sub-arrays in quick sort

• Recursion is used to randomly shuffle the elements in quick sort

• Recursion is used to divide the array into smaller sub-arrays and then sort them separately.

Given the array [14, 7, 3, 12, 9, 11, 6, 2], perform the QuickSort algorithm to sort it in ascending order. Outline the array after the first partitioning step. If the pivot is 9, identify the elements smaller than the pivot and those greater than the pivot after the initial partitioning.

• Pivot: 9, Elements < Pivot: [7, 3, 6, 2], Elements > Pivot: [14, 12, 11]

• Pivot: 6, Elements < Pivot: [3, 2], Elements > Pivot: [14, 7, 12, 9, 11]

• Pivot: 9, Elements < Pivot: [7, 3, 12, 9, 11, 6, 2]

• Pivot: 9, Elements < Pivot: [2], Elements > Pivot: [14, 7, 12, 9, 11, 6]