Counting Sort Multiple Choice Questions and Answers (MCQs)

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

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

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

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

5. It is not possible to implement counting sort when any of the input element has negative value.
a) True
b) False
View Answer

6. Which of the following sorting techniques is stable?
a) quick sort
b) counting sort
c) heap sort
d) selection sort
View Answer

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

8. What is the average time complexity of counting sort?
a) O(n)
b) O(n+k) k=range of input
c) O(n²)
d) O(n log n)
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) counting sort
d) gnome sort
View Answer

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

11. Counting sort is often used as a sub routine for radix sort.
a) true
b) false
View Answer

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

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

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

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

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]