This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Comb Sort”.
1. Comb sort is an improved version of _______
a) Selection sort
b) Bubble sort
c) Insertion sort
d) Merge sort
View Answer
Explanation: Comb sort compares two elements at a variable gap from each other in each iteration unlike bubble sort where the gap remains 1. This reduces the average time complexity of comb sort.
2. The gap between two elements being compared shrinks by a factor of _______ after every iteration.
a) 1.1
b) 1.2
c) 1.3
d) 1.4
View Answer
Explanation: It has been found experimentally that the gap between the two elements should shrink by a factor of 1.3 after each iteration for the most efficient sorting.
3. The initial gap between two elements being compared _______
a) is equal to number of elements in the array
b) is equal to 1.3
c) depends on the number of iterations
d) depends on the compiler being used
View Answer
Explanation: Initial gap is taken to be equal to the number of elements in the array and shrinks by a factor of 1.3 in each iteration, initial gap is independent of the number of iterations and compiler being used.
4. What is the worst case time complexity of comb sort?
a) O(n2)
b) O(n log n)
c) O(n)
d) O(n2/2a) (a=number of increment)
View Answer
Explanation: Worst case complexity is observed when the input array is reverse sorted. This is same as the worst case complexity of bubble sort.
5. The gap value after 3 iterations in an array with 6 elements will be _______
a) 4
b) 3
c) 2
d) 1
View Answer
Explanation: Initially the gap value will be 6. For the first iteration, it will be 6/1.3=4 then 4/1.3=3 for second iteration and 3/1.3=2 for the third iteration.
6. Auxiliary space used by comb sort is _______
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Explanation: Auxiliary space used by comb sort is O(1) as it does not use any extra space for manipulating the input.
7. The given array is arr={7,4,5,8,1,2}. The number of iterations required to sort the array using comb sort and bubble sort respectively will be _______
a) 7 and 8
b) 5 and 6
c) 5 and 5
d) 4 and 5
View Answer
Explanation: Comb sort takes 1 iteration less as compared to bubble sort as it makes use of variable gap value whereas bubble sort uses a constant gap value of 1.
8. Comb sort is a stable sorting algorithm.
a) True
b) False
View Answer
Explanation: Comb sort is not a stable sorting algorithm as it does not sort the repeated elements in the same order as they appear in the input.
9. What is the best case time complexity of comb sort and bubble sort respectively?
a) O(n2) and O(n log n)
b) O(n log n) and O(n)
c) O(n) and O(n2)
d) O(n2/2a) (a=number of increment) and O(n2)
View Answer
Explanation: Best case complexity for comb sort and bubble sort is O(n log n) and O(n) respectively. It occurs when the input array is already sorted.
10. What is the advantage of comb sort over merge sort?
a) Comb sort is an in place sorting algorithm
b) Comb sort is a stable sorting algorithm
c) Comb sort is more efficient
d) It has no advantage
View Answer
Explanation: Comb sort does not require auxiliary space for manipulating input so it is an in place sorting algorithm but merge sort does require O(n) of auxiliary space which makes comb sort better in terms of space complexity.
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]
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
- Practice Data Structure MCQ
- Apply for Computer Science Internship
- Check Programming Books
