Draw the right half of the decision tree for Insertion Sort on an array of size

Question

Draw the right half of the decision tree for Insertion Sort on an array of size n = 4. In other words, assume that the first comparison a_1: a_2 always satisfies a_1 > a_2. This problem has to do with stable sorting algorithms. Recall from the class that we claimed that counting sort is a stable sorting algorithm. Prove that counting sort is in fact stable. Is deterministic quicksort (i.e. when we always choose the first element to be the pivot) a stable sorting algorithm? Prove that it is stable or give an example for which it produces an unstable result. This problem has to do with the choice of a pivot in quicksort. Describe the property that the pivot must satisfy in order for quicksort to have its best-case running time. Explain how the order statistics algorithm described in class can be used to generate a good pivot. What is the worst-case running time of this algorithm? What is the expected running time of this algorithm?

Explanation / Answer

2)

             a)

b)

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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