Design and Analysis of Algorithms Questions - Shell Sort Part-2

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

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

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

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

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

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.

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

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.

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

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.

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

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

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

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.

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

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

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

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

10. On which algorithm is heap sort based on?
a) Fibonacci heap
b) Binary tree
c) Priority queue
d) FIFO

Answer: c
Explanation: Heap sort is based on the algorithm of priority queue and it gives the best sorting time.



Design and Analysis of Algorithms

The Prelude to Sorting Symphony


In the grand theater of algorithms, sorting is like orchestrating a symphony. Each element plays a note, and Shell Sort steps in as the charismatic conductor, waving its wand to create harmony. But what makes it so special?

Breaking Down the Algorithmic Ballet


You have a list of elements, and you want to arrange them in ascending or descending order. Shell Sort, also known as the diminishing increment sort, is your magical wand. It's a smart cookie, starting with larger gaps and gradually narrowing them down until the list is nearly sorted.

The Dance of Gaps


In Shell Sort, gaps are the choreography that dictates the movement of elements. The algorithm begins with a big leap, comparing elements that are far apart. Then, it progressively shrinks the gap, creating a mesmerizing dance of data until, voilà, everything is in order.

Why Shell Sort Rules the Sorting Ball


Unlike some other sorting algorithms, Shell Sort doesn't just move elements one step at a time. It's like giving your data a dance partner that can waltz across the list, making it faster and more efficient.

Wrapping Up the Algorithmic Soirée


In the grand finale of our sorting symphony, Shell Sort takes a bow, leaving behind an ordered array of applause. The design and analysis of algorithms, intertwined with MCQs, applaud this sorting maestro for its dance of efficiency.

So, next time you're pondering the algorithmic universe, remember Shell Sort – the magical conductor orchestrating the data ballet with elegance and precision. Keep sorting, keep dancing, and let the algorithmic show go on!