Question

Which of the following is true?

(a) Shell sort’s passes completely sort the elements before going on to the next-smallest gap while Comb sort’s passes do not completely sort the elements

(b) Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap like in Comb sort

(c) Comb sort’s passes completely sort the elements before going on to the next-smallest gap like in Shell sort

(d) Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap while Comb sort’s passes completely sort the elements

This question was addressed to me in unit test.

Origin of the question is Shell sort in division Sorting of Data Structures & Algorithms II

Answer 1

The correct choice is (a) Shell sort’s passes completely sort the elements before going on to the next-smallest gap while Comb sort’s passes do not completely sort the elements

Explanation: Both Shell sort and Comb sort have repeated sorting passes with decreasing gaps. Unlike Comb sort, in Shell sort the array is sorted completely in each pass before going on to the next-smallest gap.