Problem 1. [14 points] Sorting: Read the assigned chapter and the notes for Week

Question

Problem 1. [14 points] Sorting: Read the assigned chapter and the notes for Week 7 located in the e cil Learning Activities area, and then do the following problems: (a) 12 points Both the Merge Sort and the Quick Sort algorithms will sort a list by portioning the list. Briefly explain how Merge Sort differs from Quick Sort when partitioning the list. (b) 12 points] What is the big-O of the she1lsort function provided in Figure 7.6 on page 297? Briefly explain how you arrived at your answer. Remember big-O measures the worst case runtime scenario.

Explanation / Answer

a) Partitioning in merge sort is always done usign middle element of the array and thus array will always be partitioned in equal halves. In quick sort partitioning is based upon the pivot element, after a complete iteration, pivot element is placed at the right place in the list and array will be partitioned by this position, which makes size of both the paritions unpredictable depending upon the array and sizes of both the partition may or may not be the same.

b) Worst case running time complexity of given algorithm is O(n2) when all the elements will be shifted by the innermost loop.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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