Comb Sort – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

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

1. Auxiliary space used by comb sort is _______
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)

Explanation: Comb sort uses O(1) auxiliary space so it does not require any additional space to manipulate the input.

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

Explanation: Since comb sort uses a variable gap value rather than a fixed gap value of 1, it takes one iteration less than bubble sort.

3. Comb sort is a stable sorting algorithm.
A) True
B) False

Explanation: Since it does not sort repeated elements in the same order as they appear in the input, comb sort is not a stable sorting algorithm.

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

Explanation: Comb sort and bubble sort have best-case complexity of O(n log n) and O(n), respectively. When the input array is already sorted, this error occurs.

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

Explanation: Comb sort does not require auxiliary space for input manipulation, making it an in place sorting algorithm, while merge sort does, requiring O(n) of auxiliary space, making comb sort more space efficient.

6. Comb sort is an improved version of _______
A) Selection sort
B) Bubble sort
C) Insertion sort
D) Merge sort

Explanation: In contrast to bubble sort, where the difference between two elements remains constant, comb sort compares two elements at a variable distance from each other in each iteration. The average time complexity of comb sort is reduced as a result.

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

Explanation: For the most effective sorting, the distance between the two elements should shrink by a factor of 1.3 after each iteration, according to experiments.

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

Explanation: The initial gap is set to the number of elements in the array and shrinks by a factor of 1.3 for each iteration; the initial gap is unaffected by the number of iterations or compiler used.

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

Explanation: When the input array is reverse sorted, the worst case complexity is observed. This is the same as the bubble sort’s worst case complexity.

10. The gap value after 3 iterations in an array with 6 elements will be _______
A) 4
B) 3
C) 2
D) 1

Explanation: The distance value will be 6 at first. It will be 6/1.3=4 for the first iteration, 4/1.3=3 for the second iteration, and 3/1.3=2 for the third iteration.

Wodzimierz Dobosiewicz and Artur Borowy created Comb sort in 1980, and it was later rediscovered (and given the name “Combsort”) by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort in the same way that Shellsort improves on insertion sort. The basic concept is to get rid of turtles, or small values at the end of the list, which slow down the sorting process considerably in a bubble sort. In bubble type, rabbits, or large values near the start of the list, are not a concern.

Leave a Reply

Your email address will not be published. Required fields are marked *