# Shell Sort Multiple Choice Questions and Answers

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

1. What is the other name for a shell sort algorithm?
a) Diminishing increment sort
b) Diminishing decrement sort
c) Insertion sort
d) Selection sort
View Answer

Answer: a
Explanation: The other name for a shell sort algorithm is diminishing decrement sort as the distance between comparisons decreases as the algorithm runs until the last phase.

2. The worst case running time of shell sort, using Shell’s increments is?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
View Answer

Answer: d
Explanation: The lower bound of a shell sort algorithm is mathematically found to be O(N2).

3. Who invented the shell sort algorithm?
a) John Von Neumann
b) Donald Shell
c) Tony Hoare
d) Alan Shell
View Answer

Answer: b
Explanation: Shell sort algorithm is invented by Donald shell. Merge sort is invented by John Von Neumann. Quick sort is invented by Tony Hoare.
advertisement
advertisement

4. Shell sort algorithm is the first algorithm to break the quadratic time barrier.
a) True
b) False
View Answer

Answer: a
Explanation: Shell sort broke the quadratic time barrier as it works by comparing elements that are distant.

5. Shell sort algorithm is an example of?
a) External sorting
b) Internal sorting
c) In-place sorting
d) Bottom-up sorting
View Answer

Answer: b
Explanation: Shell sort is an example of internal sorting because sorting of elements is done internally using an array.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Shell sort uses a sequence called a incrementing sequence to sort the elements.
a) True
b) False
View Answer

Answer: a
Explanation: Shell sort uses an increment sequence h1, h2, h3… and this sequence will work as long as h1=1.

7. Which of the following sorting algorithms is closely related to shell sort?
a) Selection sort
b) Merge sort
c) Insertion sort
d) Bucket sort
View Answer

Answer: c
Explanation: Shell sort performs an insertion sort on hk independent arrays. It is mainly a variation of insertion sort.
advertisement

8. Why is Shell sort called as a generalization of Insertion sort?
a) Shell sort allows an exchange of far items whereas insertion sort moves elements by one position
b) Improved lower bound analysis
c) Insertion is more efficient than any other algorithms
d) Shell sort performs internal sorting
View Answer

Answer: a
Explanation: Shell sort is an extension of insertion sort because it swaps elements at far distances and at a faster rate.

9. Given an array of the following elements 81,94,11,96,12,35,17,95,28,58,41,75,15.
What will be the sorted order after 5-sort?
a) 11,12,15,17,28,35,41,58,75,81,94,95,96
b) 28,12,11,35,41,58,17,94,75,81,96,95,15
c) 35,17,11,28,12,41,75,15,96,58,81,94,95
d) 12,11,15,17,81,94,85,96,28,35,41,58,75
View Answer

Answer: c
Explanation: The general strategy to hk sort is for each position, i, in hk,, hk+1,…., N-1, place the element in the correct spot among i, i-hk,i-2hk, etc.
advertisement

10. Which of the following statements is the basic for loop for a shell sort algorithm?
a) for(increment=N/2;increment>0;increment/=2)
b) for(i=1;i<n;i++)
c) for(i=n/2;i>=0;i- -)
d) for(i=0;i< n;i++;numelements- -)
View Answer

Answer: a
Explanation: for(increment=N/2;increment>0;increment/=2) represents shell sort, for(i=1;i<n;i++) represents insertion sort, for(i=n/2;i>=0;I- -) represents heap sort, for(i=0;i<n;i++;numelements- -) merge sort.

11. On how many increment sequences does the worst case analysis of shell sort depends?
a) one
b) two
c) three
d) four
View Answer

Answer: c
Explanation: The worst case analysis of shell sort depends on two increment sequences- using Shell’s increments, Sedgewick’s and Hibbard’s increments.

12. What is the worst case running time of shell sort using Hibbard’s increments?
a) O(N)
b) O(N2)
c) O(N1/2)
d) O(N3/2)
View Answer

Answer: d
Explanation: Mathematically, the lower bound analysis for shell sort using Hibbard’s increments is O(N3/2).

13. What is the general form of Shell’s increments?
a) 1,2,3,…,n
b) 1,3,7,….,2k-1
c) 1,3,5,7,….,k-1
d) 1,5,10,15,…, k-1
View Answer

Answer: b
Explanation: Shell’s increments are of the form 1,3,7,….,2k-1. The key difference is that the consecutive elements have no common factors.

14. What is the worst case analysis of shell sort using Shell’s increments?
a) O(N)
b) O(N2)
c) O(N1/2)
d) O(N3/2)
View Answer

Answer: b
Explanation: The worst case analysis is mathematically found to be O(N2). The proof is rather complicated.

15. What is the worst case analysis of Shell sort using Sedgewick’s increments?
a) O(N2)
b) O(N3/2)
c) O(N4/3)
d) O(N5/4)
View Answer

Answer: c
Explanation: The worst case analysis of Shell sort using Sedgewick’s increments is mathematically calculated to be O(N4/3).

More MCQs on Shell Sort:

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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.