3. Define a sorting algorithm to be parsimonious i it never compares the same pa

Question

3. Define a sorting algorithm to be parsimonious i it never compares the same pair of input values twice. (Assume that all the values being sorted are distinct.) For example, it was shown in the notes that quicksort is parsimonious. (a) Is insertion sort parsimonious? Justify your answer with either a counterexample (b) Is merge sort parsimonious? Justify your answer with either a counterexample (c) Is heap sort parsimonious? Justify your answer with either a counterexample or or a brief argument or a brief argument a brief argument

Explanation / Answer

Solution:

A)  Insertion sort is parsimonious:

In insertion sort, after round k, the first k+1 elements are sorted. in later rounds, the already sorted initial elements are never again compared which each other. rather, a new element to the right of the first k+1 elements is compared one by one with the already sorted first k+1 elements and inserted in the correct spot. so clearly, in any round, a new never before the touched element is compared with already finished elements. so since every comparison is a new element and an old one, the same comparison is never done twice.

B) Merge sort is parsimonious:

Merge sort works in thr following way. Split the array into 2 subarrays. then recursively mergesort the 2 subarrays. then combine the 2 sorted subarrays into one sorted array. all the comparisons are done in the combine stage. for any array, the recursion basically keeps going until you are left with 1 element subarrays (and 2 element subarrays if the total number of elements in the array is not a perfect power of 2). then the single elements of two 1-element subarrays are compared to see which is smaller and put together to form a sorted 2-element subarray. now the crucial part is this. the elements of that 2-element subarray will never be compared with each other again. instead, they will only be compared against elements of another 2-element subarray in a later combine stage. this will form a sorted 4-element subarray. once again, the elements of this 4-element subarray will never be compared with each other again. they will only be compared with elements of another 4-element subarray in a later combine stage. (and of course, the 2 sorted 4-element subarrays were formed independently in a different branch of the recursion tree, so any comparison between their elements could not have been done before). also, we must note that in a single combine stage, after any comparison between 2 values, the smaller of the 2 is put away inside "finished" array and never touched again in that combine stage, so there are no repeated comparisons within a single combine stage either.

thus, all comparisons happen on the combine stage. no comparison done in one combine stage will ever happen again in another combine stage. and no comparison done in one combine stage will ever happen again in that same combine stage. so no comparison is done twice.

C) Heap sort is not parsimonious - Heapsort counterexample:

C B A. The keys A and B get compared twice, once in the heap construction phase (when sinking C) and once in the sort down phase (when sinking A after C and A are exchanged). Hence this is non-parsimonious.

Please, please upvote and ask your doubts in the comments.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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