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

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

1. Which of the following sorting techniques is stable?
A) quick sort
B) counting sort
C) heap sort
D) selection sort

Explanation: The elements with similar values appear in the same order in the output array as they did in the input array, making counting sort a stable sorting algorithm.

2. Which of the following uses the largest amount of auxiliary space for sorting?
A) Bubble sort
B) Counting sort
C) Quick sort
D) Heap sort

Explanation: Fast sort, bubble sort, and heap sort are in place sorting techniques, while counting sort needs O(n+k) auxiliary space. As a result, counting type takes up the most extra space.

3. What is the average time complexity of counting sort?
A) O(n)
B) O(n+k) k=range of input
C) O(n2)
D) O(n log n)

Explanation: Counting sort has an O(n+k) time complexity since it takes k time to count the occurrences of each element in the input range and n time to find the right index value for each element in the sorted array.

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) counting sort
D) gnome sort

Explanation: In all three cases, the time complexity of counting type remains constant. O(n+k) is the formula.

5. Which of the following statement is true about comparison based sorting?
A) counting sort is a comparison based sort
B) any comparison based sorting can be made stable
C) bubble 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 strategy can be made more robust by using a location as a criterion.

6. Counting sort is often used as a sub routine for radix sort.
A) true
B) false

Explanation: Counting sort is used as a sub routine for radix sort as it is a stable and non comparison based sorting algorithm.

7. What is the advantage of counting sort over quick sort?
A) counting sort has lesser time complexity when range is comparable to number of input elements
B) counting sort has lesser space complexity
C) counting sort is not a comparison based sorting technique
D) it has no advantage

Explanation: When the range of input elements is comparable to the number of input elements, counting sort is very effective since it performs sorting in linear time.

8. which of the following represents the algorithm of counting sort correctly?
A)

```  function countingSort(array, k) is
count ← new array of k zeros
for i = 1 to length(array) do
count[array[i]] ← count[array[i]] + 1
for i = 2 to k do
count[i] ← count[i] + count[i +1]
for i = length(array) downto 1 do
output[count[array[i]]] ← array[i]
count[array[i]] ← count[array[i]] - 1
return output```

B)

```  function countingSort(array, k) is
count ← new array of k zeros
for i = 1 to length(array) do
count[array[i]] ← count[array[i]] + 1
for i = 2 to k do
count[i] ← count[i] + count[i - 1]
for i = length(array) downto 1 do
output[count[array[i]]] ← array[i]
count[array[i]] ← count[array[i]] - 1
return output```

C)

```  function countingSort(array, k) is
count ← new array of k zeros
for i = 1 to length(array) do
count[array[i]] ← count[array[i]] + 1
for i = 1 to k do
count[i] ← count[i] + count[i - 1]
for i = length(array) downto 1 do
output[count[array[i]]] ← array[i]
count[array[i]] ← count[array[i]] - 1
return output```

D)

```  function countingSort(array, k) is
count ← new array of k zeros
for i = 1 to length(array) do
count[array[i]] ← count[array[i]] + 1
for i = 2 to k do
count[i] ← count[i] + count[i + 1]
for i = length(array) downto 1 do
output[count[array[i]]] ← array[i]
count[array[i]] ← count[array[i]] - 1
return output```

Explanation: The first loop counts the number of times each variable appears. The second loop calculates the prefix amount on count to evaluate the location range in which objects with that key should be stored. The third loop puts each element in its proper location.

9. What is the disadvantage of counting sort?
A) counting sort has large time complexity
B) counting sort has large space complexity
C) counting sort is not a comparison based sorting technique
D) counting sort cannot be used for array with non integer elements

Explanation: Since an array of frequencies cannot be built without counting type, it can only be used for arrays of integer elements.

10. Which of the following algorithm takes non linear time for sorting?
A) counting sort
B) quick sort
C) bucket sort
D) radix sort

Explanation: Fast sort takes O(n log n) time to sort, so it is non linear, while counting sort, bucket sort, and radix sort take linear time to sort.

11. How many comparisons will be made to sort the array arr={1,5,3,8,2} using counting sort?
A) 5
B) 7
C) 9
D) 0

Explanation: Since counting sort is an example of a non-comparison sort, it can sort an array without comparing it.

12. Which of the following is not an example of non comparison sort?
A) bubble sort
B) counting sort
C) radix sort
D) bucket sort

Explanation: Bubble sort is not a non-comparison sort since it requires comparing array elements to sort an array.

13. Which of the following sorting techniques is most efficient if the range of input data is not significantly greater than a number of elements to be sorted?
A) selection sort
B) bubble sort
C) counting sort
D) insertion sort

Explanation: The counting sort has a time complexity of O(n+k), where n is the number of input elements and k is the input range. As a result, if the input range is not substantially greater than the number of elements in the array, it is very effective.

14. What is the auxiliary space requirement of counting sort?
A) O(1)
B) O(n)
C) O(log n)
D) O(n+k) k=range of input

Explanation: To sort the input array, counting sort requires two additional arrays. The size of the first array is k because it must store the count of all the elements that fall within the range of input data elements. Since the second array must store the input elements in a sorted order, its size is n. As a result, the total amount of auxiliary space available is O(n+k).

15. It is not possible to implement counting sort when any of the input element has negative value.
A) True
B) False

Explanation: The counting sort algorithm can also be extended to include negative numbers. In this case, the 0th index is used to store the minimum element.

Counting sort is an integer sorting algorithm used in computer science for sorting a list of items according to keys that are small integers. It works by counting the number of items for each unique key value and then applying arithmetic to those counts to decide where each key value should appear in the output series. Since its running time is proportional to the number of items and the difference between the maximum and minimum key values, it is only appropriate for direct use in cases where the number of items is not substantially greater than the variance in keys.

5. It is not possible to implement counting sort when any of the input element has negative value.
a) True
b) False
View AnswerAnswer: b
Explanation: It is possible to extend the counting sort algorithm for negative numbers as well. In such a case we store the minimum element at the 0th inde