1Quick Sort 3. A random list 4. Doesn\'t matter Question 18 (2 points) Regarding

Question

1Quick Sort 3. A random list 4. Doesn't matter Question 18 (2 points) Regarding Shell's sort, explain why it is considered a modified version of the insertion sort. Also, explain how that, even though the incrementing variable k shrinks with each pass, causing more checks, the process actually becomes more efficient as we do more passes. AV Save Question 19 (1 point) Given that we could have any sequence of numbers, but the case that causes the worst efficiency for the quick sort is a common occurrence, what is the best way to avoid having your program run in this worst case time?

Explanation / Answer

Shell's sort is considered to be a modified version of insertion sort as we do swapping of every consecutive element in insertion sort, while in Shell's sort we have a gap or pass of predefined length, and we do swapping reducing the pass length by 1 with every iteration.

Insertion sort and Shell sort both are O(n2) algorithms, in insertion sort we swap every next element but in shell's sort we swap element from large gap, (decreasing gap to 1) but in many cases, elements far apart only need to be swapped, in that case, insertion sort would swap every element, but shell's sort would do it more efficiently as it can swap elements which are far apart.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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