Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ’s – Quicksort – 3

1 - Question

 QuickSort can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
View Answer

Answer: b
Explanation: First you divide(partition) the array based on the pivot element and sort accordingly.


2 - Question

Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is the ending index of the array, partition returns the pivot element, we will see the code for partition very soon)
a)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot-1);
		quickSort(arr, pivot+1, high);
}
}

b)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high<low)
{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot-1);
		quickSort(arr, pivot+1, high);
}
}

c)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot);
		quickSort(arr, pivot, high);
}
}

d)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot);
		quickSort(arr, pivot+2, high);
}
}
View Answer

Answer: a
Explanation: Based on the pivot returned by the call to partition, recursive calls to quickSort sort the given array.


3 - Question

What is the worst case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer

Answer: d
Explanation: When the input array is already sorted.


4 - Question

What is a randomized QuickSort?
a) The leftmost element is chosen as the pivot
b) The rightmost element is chosen as the pivot
c) Any element in the array is chosen as the pivot
d) A random number is generated which is used as the pivot
View Answer

Answer: c
Explanation: QuickSort is randomized by placing the input data in the randomized fashion in the array or by choosing a random element in the array as a pivot.


5 - Question

Which of the following code performs the partition operation in QuickSort?
a)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
	left = low;
	right = high;
while(left > right)
{
while(arr[left] <= pivot_item)
{
			left++;
}
while(arr[right] > pivot_item)
{
			right--;
}
if(left < right)
{
			swap(arr, left, right);
}
}
	arr[low] = arr[right];
	arr[right] = pivot_item;
return right;
}

b)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
	left = low;
	right = high;
while(left <= right)
{
while(arr[left] <= pivot_item)
{
			left++;
}
while(arr[right] > pivot_item)
{
			right--;
}
if(left < right)
{
			swap(arr, left, right);
}
}
	arr[low] = arr[right];
	arr[right] = pivot_item;
return right;
}

c)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
	left = low;
	right = high;
while(left <= right)
{
while(arr[left] > pivot_item)
{
			left++;
}
while(arr[right] <= pivot_item)
{
			right--;
}
if(left < right)
{
			swap(arr, left, right);
}
}
	arr[low] = arr[right];
	arr[right] = pivot_item;
return right;
}

d)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
	left = low;
	right = high;
while(left > right)
{
while(arr[left] > pivot_item)
{
			left++;
}
while(arr[right] <= pivot_item)
{
			right--;
}
if(left < right)
{
			swap(arr, left, right);
}
}
	arr[low] = arr[right];
	arr[right] = pivot_item;
return right;
}
View Answer

Answer: b
Explanation: The array is partitioned such that the elements left to the pivot are lesser than the pivot while the elements right of the pivot are greater than the pivot.


6 - Question

What is the best case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer

Answer: a
Explanation: The array is partitioned into equal halves, using the Divide and Conquer master theorem, the complexity is found to be O(nlogn).


7 - Question

The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 3
b) 3 and 1
c) 2 and 6
d) 6 and 2
View Answer

Answer: a
Explanation: The call to partition returns 1 and 3 as the pivot elements.


8 - Question

What is the average case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer

Answer: a
Explanation: The position of partition(split) is unknown, hence all(n) possibilities are considered, the average is found by adding all and dividing by n.


9 - Question

 The given array is arr = {2,6,1}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 6
b) 6 and 1
c) 2 and 6
d) 1
View Answer

Answer: d
Explanation: There is only one pivot with which the array will be sorted, the pivot is 1.


10 - Question

Which of the following is not true about QuickSort?
a) in-place algorithm
b) pivot position can be changed
c) adaptive sorting algorithm
d) can be implemented as a stable sort
View Answer

Answer: b
Explanation: Once a pivot is chosen, its position is finalized in the sorted array, it cannot be modified.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners