Introduction to Algorithms. Exam Study Questions Define what a stable sorting al

Question

Introduction to Algorithms. Exam Study Questions

Define what a stable sorting algorithms is. Suppose that we have a sorting algorithm named UnstableSort which is used to sort integer numbers, anti which is known to be unstable, comprasion based and the must efficient sorting algorithm possible. We ran have the following stable sorting algorithm based on UnstableSort: Let T_s(n), T_u(n), T_pre(n) and T_post(n) be the worst case running times of StableSort, UnstableSort, Preprocess and Postprocess algorithms respectively. If we know T_s(n) = Theta(T_u(n)), what, ran you say about the T_pre(n) and T_post(n) (give asymptotic hounds for them). Give pseudo code implementations of Preprocess and Postprocess algorithms that satisfy the asymptotic bounds you found in (i).

Explanation / Answer

Stable sorting algorith keeps order of duplicate keys
For example insertion sort and merge sort are of stable sorting algorithms

Pre-process algorithm

It makes preprocessing of data for the sorting to be applied.

Post-Processing of data after sorting for the memory sake.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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