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

**1. Shell sort uses a sequence called a incrementing sequence to sort the elements.****A) True**

B) False**Explanation:** Shell sort uses the h1, h2, h3… increment series. As long as h1=1, this sequence will work.

**2. Which of the following sorting algorithms is closely related to shell sort?**

A) Selection sort

B) Merge sort**C) Insertion sort**

D) Bucket sort**Explanation: **On hk independent arrays, shell sort performs an insertion sort. It’s essentially an insertion type variant.

**3. 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**Explanation: **Shell sort is a variation of insertion sort in that it switches elements at a higher rate and over longer distances.

**4. 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**Explanation: **The general strategy for hk sorting is to place the element in the correct spot among I i-hk,i-2hk, etc. for each location, I in hk,, hk+1,…., N-1.

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

**6. On how many increment sequences does the worst case analysis of shell sort depends?**

A) one

B) two**C) three**

D) four**Explanation:** Shell sort’s worst-case analysis is based on two increment sequences: Shell’s increments, Sedgewick’s increments, and Hibbard’s increments.

**7. What is the worst case running time of shell sort using Hibbard’s increments?**

A) O(N)

B) O(N^{2})

C) O(N^{1/2})**D) O(N ^{3/2})**

**Explanation:**The lower bound analysis for shell sort using Hibbard’s increments is O(N3/2) mathematically.

**8. 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**Explanation: **The increments used by Shell are of the type 1,3,7,….,2k-1. The main difference is that there are no common factors between the elements.

**9. What is the worst case analysis of shell sort using Shell’s increments?**

A) O(N)**B) O(N ^{2})**

C) O(N

^{1/2})

D) O(N

^{3/2})

**Explanation:**Mathematically, the worst-case scenario is found to be O. (N2). The evidence is a little tricky.

**10. What is the worst case analysis of Shell sort using Sedgewick’s increments?**

A) O(N^{2})

B) O(N^{3/2})**C) O(N ^{4/3})**

D) O(N

^{5/4})

**Explanation:**The worst-case study of Shell sort using Sedgewick’s increments is O(N4/3), according to math.

**11. What is the other name for a shell sort algorithm?****A) Diminishing increment sort**

B) Diminishing decrement sort

C) Insertion sort

D) Selection sort**Explanation:** The gap between comparisons decreases as the algorithm runs until the last step, giving it another name: diminishing decrement form.

**12. 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(N ^{2})**

**Explanation:**The lower bound of a shell sort algorithm is considered to be O mathematically (N2).

**13. Who invented the shell sort algorithm?**

A) John Von Neumann**B) Donald Shell**

C) Tony Hoare

D) Alan Shell**Explanation: **Donald Shell invented the shell sort algorithm. John Von Neumann is the inventor of the merge sort. Tony Hoare is the inventor of the fast kind.

**14. Shell sort algorithm is the first algorithm to break the quadratic time barrier.****A) True**

B) False**Explanation: **Shell sort, which compares elements that are far apart, broke the quadratic time barrier.

**15. Shell sort algorithm is an example of?**

A) External sorting**B) Internal sorting**

C) In-place sorting

D) Bottom-up sorting**Explanation: **Since the sorting of elements is performed internally using an array, shell sort is an example of internal sorting.

**16. Shell sort is an improvement on ____****A) insertion sort**

B) selection sort

C) binary tree sort

D) quick sort**Explanation:** Shell sort is a variant of insertion sort that allows for the exchange of elements that are separated by a large distance. The shell sort algorithm sorts the original input array into sub-arrays. Every hth element of the original array is contained in these sub-arrays.

**17. 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****Explanation: **7-sorted arrays become 7-ordered arrays. And a 5-sorted array becomes a 5-ordered array. When a k-ordered array is h-sorted, it retains its original order. As a result, a 7-sorted array that is then 5-sorted becomes both 7-ordered and 5-ordered.

**18. If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2 ^{k}–1) are used in a Shell sort implementation, then the best case time complexity will be ________**

**A) O(nlogn)**

B) O(n)

C) O(n

^{2})

D) O(logn)

**Explanation:**

When the list is already sorted, the best case scenario occurs. The number of comparisons for each of the increments-based insertion sorts should, in the best case, be equal to the length of the array.

Here, 2k –1 n is the number of records, and n is the number of records. So k = log(n+1), and the sorting time is less than n * log(n+1) in the best case. As a result, the best-case time complexity is O. (nlogn).

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

**20. Shell sort is more efficient than insertion sort if the length of input arrays is small.**

A) True**B) False****Explanation:** If the array length is limited, insertion sort is more effective than Shell sort because it is easier to programme and involves few actions other than comparisons and replacements on each run.

**21. 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**Explanation:** Shell sort and Comb sort both have several sorting passes with smaller gaps between them. Shell sort, unlike Comb sort, sorts the entire array in each move before moving on to the next-smallest gap.

**22. Shell sort is also known as _____________**

A) diminishing decrement sort**B) diminishing increment sort**

C) partition exchange sort

D) diminishing insertion sort**Explanation:** Since each pass is determined by an increment h, only records that are h units apart will be sorted, shell sort is also known as diminishing increment sort.

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

**Explanation:**The relative order of elements with equal values may change in Shell type. As a result, it isn’t a reliable sorting method. Since it needs O(1) auxiliary space, shell sort is an in-place sorting algorithm.

**24. 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**Explanation: **Given elements 27 59 49 37 15 90 81 39,

First Iteration (span = 5):

So, the sequence after first iteration will be, 27 59 39 37 15 90 81 49.

**25. 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 ;< 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] ****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.

Shellsort is an in-place comparison sort also known as Shell sort or Shell’s process. It can be seen as either a generalisation of bubble sorting or a generalisation of insertion sorting (insertion sort). The method begins by sorting pairs of elements that are far apart, then gradually closes the distance between the elements to be compared. It can shift some out-of-place elements into position faster than a simple nearest neighbour exchange since it starts with far apart elements. In 1959, Donald Shell released the first version of this kind. Shellsort’s execution time is strongly influenced by the gap sequence it employs.