Foundation of algorithms chp 7 #8 8. algorithm called Shell Sort is inspired nse

Question

Foundation of algorithms chp 7 #8
8. algorithm called Shell Sort is inspired nsertion Sort's ability to take by advantage order of the elements in the list. In Sort, the entire of the sublists whose elements are a distance h apart divided into noncontiguous sorted using Insertion Sort. for some number h. Each sublist is then During the next pass, the value of h is reduced, increasing the size of each the value of each h is chosen to be relatively p to its previous value. The final pass for h to sort the list Write an algorithm for Shell Sort, study its performance, and compare the result with 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.
// shift earlier gap-sorted elements up until
// the correct location for a[i] is found
3. for j=i; j>=gap && A[j-gap]>temp;j-=gap
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 F
• Subjects

---

---

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