Shell Sort Multiple Choice Questions and Answers (MCQs) – 2

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

1. Shell sort is also known as _____________
a) diminishing decrement sort
b) diminishing increment sort
c) partition exchange sort
d) diminishing insertion sort
View Answer

Answer: b
Explanation: Shell sort is also known as diminishing increment sort since each pass is defined by an increment h such that only the records which are h units apart will be sorted.

2. Statement 1: Shell sort is a stable sorting algorithm.
Statement 2: Shell sort is an in-place sorting algorithm.
a) Both statements are true
b) Statement 2 is true but statement 1 is false
c) Statement 2 is false but statement 1 is true
d) Both statements are false
View Answer

Answer: b
Explanation: In Shell sort, the relative order of elements with equal values may change. Therefore, it is not a stable sorting algorithm. Shell sort is an in-place sorting algorithm as it requires O(1) auxiliary space.

3. Shell sort is applied on the elements 27 59 49 37 15 90 81 39 and the chosen decreasing sequence of increments is (5,3,1). The result after the first iteration will be
a) 27 59 49 37 15 90 81 39
b) 27 59 37 49 15 90 81 39
c) 27 59 39 37 15 90 81 49
d) 15 59 49 37 27 90 81 39
View Answer

Answer: c
Explanation: Given elements 27 59 49 37 15 90 81 39,
First Iteration (span = 5):
The sequence after first iteration will be 27 59 39 37 15 90 81 49
So, the sequence after first iteration will be, 27 59 39 37 15 90 81 49.
advertisement
advertisement

4. Consider the following code snippet, which implements the Shell sort algorithm.

shellSort( int elements[], int num_elements , int incrmnts[], int num_incrmnts)
{
	int incr, j, k, span, y;
	for(incr = 0; incr ;&lt num_incrmnts; incr++)
	{
		span = incrmnts[incr]; data-structure-questions-answers-shell-sort
		for( j = span; j < num_elements; j++)
		{
			k = j;
			y = elements[j];
			while (________ )
			{
				elements [ k]  = elements[k - span];
				k = k - span;
			}
			elements[k] = y;
		}
	}

Which condition will correctly implement the while loop?
a) k >= j && y < elements[k- span]    
b) k >= span || y < elements[k + span]    
c) k >= j || y < elements[k + span]    
d) k >= span && y < elements[k- span]    
View Answer

Answer: d
Explanation: In Shell sort, for increment = h we sort the sub-arrays that start at arbitrary element and include every hth element.
So, if h = 4 the algorithms sorts:
Sub-array formed with elements at positions 1, 5, 9, 13 … in original array
Sub-array formed with elements at positions 2, 6, 10, 14 … in original array
Sub-array formed with elements at positions 3, 7, 11, 15 … in original array
Sub-array formed with elements at positions 4, 8, 12, 16 … in original array
Therefore, the condition given in option k >= span && y < elements[k- span] will implement while loop correctly.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

5. Shell sort is an improvement on ____
a) insertion sort
b) selection sort
c) binary tree sort
d) quick sort
View Answer

Answer: a
Explanation: Shell sort is an improvement on insertion sort that allows the exchange of elements that are far apart. Shell sort algorithm sorts separate sub-arrays of the original input array. These sub-arrays contains every hth element of the original array.
advertisement

6. An array that is first 7-sorted, then 5-sorted becomes _________
a) 7-ordered
b) 5-ordered
c) both 2-ordered and 5-ordered
d) both 7-ordered and 5-ordered
View Answer

Answer: d
Explanation: An array that is 7-sorted, becomes 7-ordered. And an array that is 5-sorted, becomes 5-ordered. If k-ordered array is h-sorted, it remains k-ordered. Thus, an array that is first 7-sorted, then 5-sorted becomes both 7-ordered and 5-ordered.

7. If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2k–1) are used in a Shell sort implementation, then the best case time complexity will be ________
a) O(nlogn)
b) O(n)
c) O(n2)
d) O(logn)
View Answer

Answer: a
Explanation: The best case occurs when the array is already sorted. In best case the number of comparison for each of the increments-based insertion sorts is equal to length of array.
Here 2k –1 < n, where n is the number of records. So k < log(n+1), thus the sorting time in best case is less the n * log(n+1). Therefore best case time complexity is O(nlogn).
advertisement

8. Records R1, R2, R3,.. RN with keys K1, K2, K3,.. KN are said to be h-ordered, if ________
a) Ki <= Ki+h for 1<= i*h <= N
b) Kh <= Ki+h for 1<= i <= N
c) Ki <= Kh for 1<= i <= h
d) Ki <= Ki+h for 1<= i <= N-h
View Answer

Answer: d
Explanation: Records are h-ordered if every hth element (starting anywhere) yields a sorted array. Therefore, given records with keys K1, K2, K3,.. KN are said to be h-ordered, if Ki <= Ki+h for 1<= i <= N-h.

9. Shell sort is more efficient than insertion sort if the length of input arrays is small.
a) True
b) False
View Answer

Answer: b
Explanation: Insertion sort is more efficient than Shell sort if the length of array is small because insertion sort is quite simple to program and involve very few actions other than comparisons and replacements on each pass.

10. 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
View Answer

Answer: a
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.

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 - Founder & CTO at Sanfoundry
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.