# Pigeonhole Sort – Multiple Choice Questions and Answers (MCQs)

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

1. Pigeonhole sort is a stable sorting algorithm.
A) true
B) false

Explanation: Pigeonhole sort is a good example of a long-lasting sorting algorithm. Since the elements with similar values appear in the output array in the same order as they did in the input array, this is the case.

2. Pigeonhole sort is an in place sorting algorithm.
A) true
B) false

Explanation: Pigeonhole sorting necessitates O(n+k) space. As a result, it does not meet the definition of an in-place sorting algorithm.

3. 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)

Explanation: Pigeonhole sort has an O(n+k) time complexity. It is made up of two loops. One loop goes from 0 to range(k), while the other goes from 0 to n, making the time complexity O(n+k).

4. 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

Explanation: In all three cases, the pigeonhole’s time complexity remains constant. O(n+k) is the formula. However, only when the number of elements is comparable to the input range is it efficient.

5. 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

Explanation: When making comparisons, any comparison-based sorting method can be made more robust by using location as a criterion. Pigeonhole sorting is a reliable sorting method.

6. 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

Explanation: Pigeonhole sort is useful when the selection is comparable to a large number of input elements since it sorts in linear time. Merge form, on the other hand, often takes O(n log n).

7. 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;
}
}```

Explanation: The maximum and minimum elements are found first in pigeonhole sort. The elements are then placed in their appropriate holes before being returned to the original collection. This sorting function sorts the input.

8. Which of the following algorithm takes linear time for sorting?
A) pigeonhole sort
B) heap sort
C) comb sort
D) cycle sort

Explanation: Pigeonhole sort has an O(n+k) linear time complexity. All of the other choices, on the other hand, have a non-linear time complexity. However, it should be noted that pigeonhole sorting is not always successful.

9. 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

Explanation: Since pigeonhole sort is a non-comparison sort, it can sort an array without performing any comparisons. As a result, no comparisons are needed.

10. Which of the following is a non-comparison sort?
A) heap sort
B) quick sort
C) merge sort
D) pigeonhole sort

Explanation: Comparison sort includes heap sort, merge sort, and fast sort, as they all include comparing array elements in order to sort an array. Pigeonhole sort, on the other hand, is a non-comparison dependent sort.

11. 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

Explanation: Pigeonhole sort is a sort that isn’t based on comparison. When the number of elements is comparable to the input range, it is most efficient.

12. 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)

Explanation: The pigeonhole sort algorithm necessitates the use of two arrays. Since the first one must store the input elements, its size is n. The pigeonhole array, which has a size equal to range k, is the second. Overall, the complexity of space is O(n+k).

13. The auxiliary array used in pigeonhole sorting is called ______________
A) bucket
B) pigeon
C) hole
D) pigeonhole

Explanation: Pigeonhole is the name of the auxiliary sequence used in pigeonhole sorting. It is used to store each element in the hole that corresponds to it.

Pigeonhole sorting is a sorting algorithm for lists of elements where the number of elements (n) and the length of the range of possible key values (N) are nearly equal. 1st It takes O(n + N) time to complete. It’s similar to counting sort, but it “moves objects twice: once to the bucket array and then to the final destination,” while counting sort “builds an auxiliary array, then uses the array to compute each item’s final destination and move the item there.” Pigeonhole is the name of the auxiliary sequence used in pigeonhole sorting. It is used to store each element in the hole that corresponds to it.