Please provide an explanation for your answer. It\'s more important that I under

Question

Please provide an explanation for your answer. It's more important that I understand it then get the right answer.

3 Quicksort (15 points) Suppose we have three arrays, each with 7 elements, and we want to use Quicksort (using the last element in the array as the pivot) to sort each array (from the smallest to the largest). Array 1: (1, 3, 4, 6, 8, 10, 12) . Array 2: (1, 4, 3, 6, 10, 8, 6). Array 3: (12, 10, 8, 6, 4, 3, 1 Which array(s) has the best-case running time, and which array(s) has the worst-case running time? Justify your answers.

Explanation / Answer

Array 1 : (1, 3, 4, 6, 8, 10, 12) => best case running-time O(n log n)
Lets assume we pick last element as pivot, array1 is already sorted in increasing order, so there wont be any swaps and its the best case.

Array 2 : (1, 4, 3, 6, 10, 8, 6) => average case running-time O(n log n)
If we pick last element as pivot, in array2 there are minimul number of swaps occurs and there wont be any change in time complexity. So, it will perform average.

Array 3 : (12, 10, 8, 6, 4, 3, 1) => worst case running-time O(n2)
Since we are picking last element as pivot, we need to swap every element of array and there will be lot of comparisons for sorting this array. Thus, it will be worst case running time.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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