8. algorithm called Shell Sort is inspired sertion Sort\'s ability to take by ad

Question

8. algorithm called Shell Sort is inspired sertion Sort's ability to take by advantage order of the elements in the list. In ents are a distance h of the sublists apart divided into noncontiguous sorted using Insertion Sort for some number h. Each sublist is then increasing the size of each d, During the next the of is chosen to be relatively p to its previous value. the value of each h 1 for h to sort the list Write an algorithm for The final pass value and compare the result with Shell Sort, study its performance, the performance of Insertion Sort.

Explanation / Answer

SHELL-SORT(A,n)
1. for gap=n/2; gap=0; gap/=2 do: // we take gap sequence in order of |N/2|, |N/4|, |N/8|...1
2. for i=gap; i<n; i+=1 do: temp=A[i] //Perform gapped insertion sort for this gap size.
3. for j=i; j>=gap && A[j-gap]>temp;j-=gap // shift earlier gap-sorted elements up until the correct location for a[i] is found
4. do:
5. A[j]= A[j-gap]
6. end for // put temp in its correct location
7. A[j]= temp;
8. end for
9. end for
end func

The insertion sort is very simple and in-place with O(N^2) time complexity, whereas shell sort is a little more complex and harder to understand, and with time complexity O(N^(5/4)).

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.