Pigeonhole Sort Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Pigeonhole Sort”.

1. How many comparisons will be made to sort the array arr={1,5,3,8,2} using pigeonhole sort?
a) 5
b) 7
c) 9
d) 0
View Answer

2. Which of the following is a non-comparison sort?
a) heap sort
b) quick sort
c) merge sort
d) pigeonhole sort
View Answer

3. In which of the following case pigeonhole sort is most efficient?
a) when range of input is less than number of elements
b) when range of input is more than number of elements
c) when range of input is comparable to the number of elements
d) when the given array is almost sorted
View Answer

4. What is the space complexity of pigeonhole sort (k=range of input)?
a) O(n*k)
b) O(n)
c) O(k)
d) O(n+k)
View Answer

5. The auxiliary array used in pigeonhole sorting is called ______________
a) bucket
b) pigeon
c) hole
d) pigeonhole
View Answer

6. Pigeonhole sort is a stable sorting algorithm.
a) true
b) false
View Answer

7. Pigeonhole sort is an in place sorting algorithm.
a) true
b) false
View Answer

8. What is the average time complexity of pigeonhole sort (k=range of input)?
a) O(n)
b) O(n+k)
c) O(n²)
d) O(n*k)
View Answer

9. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case?
a) quick sort
b) insertion sort
c) pigeonhole sort
d) bubble sort
View Answer

10. Choose the correct statement from the following.
a) pigeonhole sort is a comparison based sort
b) any comparison based sorting can be made stable
c) quick sort is not a comparison based sort
d) any comparison based sort requires at least O(n²) time
View Answer

11. What is the advantage of pigeonhole sort over merge sort?
a) pigeonhole sort has lesser time complexity when range is comparable to number of input elements
b) pigeonhole sort has lesser space complexity
c) counting sort is not a comparison based sorting technique
d) pigeonhole sort is adaptive
View Answer

12. Which of the following function represents pigeonhole sort correctly?
a)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[r]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < r; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

b)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[n]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < r; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

c)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[r]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < n; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

d)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[n]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < n; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

13. Which of the following algorithm takes linear time for sorting?
a) pigeonhole sort
b) heap sort
c) comb sort
d) cycle sort
View Answer

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]