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

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

View Answer

Explanation: As counting sort is an example of non comparison sort so it is able to sort an array without making any comparison.

2. Which of the following is not an example of non comparison sort?

a) bubble sort

b) counting sort

c) radix sort

d) bucket sort

View Answer

Explanation: Bubble sort is not an example of non comparison sort as it needs to compare array elements in order to sort an array.

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

View Answer

Explanation: Time complexity of counting sort is given as O(n+k) where n is the number of input elements and k is the range of input. So if range of input is not significantly larger than number of elements in the array then it proves to be very efficient.

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

View Answer

Explanation: Counting sort uses two extra arrays to get the input array sorted. First array is required to store the count of all the elements which fall in the range of input data elements, so its size is k. The second array is required to store the input elements in sorted manner, so its size is n. Thus overall auxiliary space required becomes O(n+k).

5. It is not possible to implement counting sort when any of the input element has negative value.

a) True

b) False

View Answer

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

6. Which of the following sorting techniques is stable?

a) quick sort

b) counting sort

c) heap sort

d) selection sort

View Answer

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

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

View Answer

Explanation: Counting sort requires auxiliary space of O(n+k) whereas quick sort, bubble sort and heap sort are in place sorting techniques. Thus counting sort requires most auxiliary space.

8. What is the average time complexity of counting sort?

a) O(n)

b) O(n+k) k=range of input

c) O(n^{2})

d) O(n log n)

View Answer

Explanation: Time complexity of counting sort is O(n+k) as counting the occurrence of each element in the input range takes k time and then finding the correct index value of each element in the sorted array takes n time.

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

d) gnome sort

View Answer

Explanation: The time complexity of counting sort remains unvaried in all the three cases. It is given by O(n+k).

10. 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(n^{2}) time

View Answer

Explanation: Any comparison based sorting technique can be made stable by considering a position as criteria while making comparisons.

11. Counting sort is often used as a sub routine for radix sort.

a) true

b) false

View Answer

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

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

View Answer

Explanation: Counting sort is very efficient in the cases where range is comparable to number of input elements as it performs sorting in linear time.

13. 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 occurrences of each element. Second loop performs prefix sum on count to determine position range where items having that key should be placed in. The third loop places each element at its correct position.

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

View Answer

Explanation: Counting sort can only be used for arrays with integer elements because otherwise array of frequencies cannot be constructed.

15. Which of the following algorithm takes non linear time for sorting?

a) counting sort

b) quick sort

c) bucket sort

d) radix sort

View Answer

Explanation: Quick sort requires O(n log n) time for sorting so it takes non linear time for sorting whereas counting sort, bucket sort and radix sort sorts in linear time.

**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__.