# 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

Answer: d
Explanation: As pigeonhole sort is an example of a non-comparison sort so it is able to sort an array without making any comparison. So 0 comparisons are required.

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

Answer: d
Explanation: Heap sort, merge sort and quick sort are examples of comparison sort as it needs to compare array elements in order to sort an array. Whereas pigeonhole sort is a non-comparison based sort.

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

Answer: c
Explanation: Pigeonhole sort is a non-comparison based sort. It is most efficient in the case where the number of elements are comparable to the input range.
advertisement
advertisement

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

Answer: d
Explanation: Pigeonhole sort algorithm requires two arrays. The first one is required to store the input elements so its size is n. The second one is the pigeonhole array and has a size equal to range k. Overall space complexity becomes O(n+k).

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

Answer: d
Explanation: The auxiliary array used in pigeonhole sorting is called pigeonhole. It is used to store every element in its corresponding hole.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

Answer: a
Explanation: Pigeonhole sort is an example of a stable sorting algorithm. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

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

Answer: b
Explanation: Pigeonhole sort requires space of O(n+k). So it does not qualify to be an in place sorting algorithm.
advertisement

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

Answer: b
Explanation: Time complexity of pigeonhole sort is O(n+k). It has two loops. One of the loops runs from 0 to range(k) and the other one runs from 0 to n so the time complexity becomes O(n+k).

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

Answer: c
Explanation: The time complexity of pigeonhole remains unvaried in all three cases. It is given by O(n+k). But it is efficient only when the number of elements is comparable to the input range.
advertisement

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(n2) time
View Answer

Answer: b
Explanation: Any comparison based sorting technique can be made stable by considering the position as criteria while making comparisons. Pigeonhole sort is a stable sort.

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

Answer: a
Explanation: Pigeonhole sort is efficient in the cases where the range is comparable to a number of input elements as it performs sorting in linear time. Whereas merge sort takes O(n log n) in any case.

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;
}
}```
View Answer
Answer: a
Explanation: In pigeonhole sort, we first find the maximum and minimum elements. Then we place the elements in their corresponding holes and then finally put them back into the original array. This sorts the given input.

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

Answer: a
Explanation: Pigeonhole sort has a linear time complexity of O(n+k). Whereas all other given options have a non linear time complexity. But it should be noted that pigeonhole sort may not be efficient in every case.

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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.