3. Define a sorting algorithm to be parsimonious if it never compares the same p

Question

3. Define a sorting algorithm to be parsimonious if 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 or a brief argument. or a brief argument. a brief argument. (b) Is merge sort parsimonos? Justify your answer with either a counterexample (c) Is heap sort parsimonious? Justify your answer with either a counterexample or

Explanation / Answer

a)in round i (starting with round 0), the minimum value from index i to the end is found and inserted into index i. then, in any given round, any comparison performed before the minimum value for the round is reached will have to be done again in some later round. Insertion sort is not parsimonious.

example: suppose array had these values
3 4 2 5
in round 0, 2 will be found to be the minimum value. but any comparison done before reaching the 2 will have to be done again in a later round. first 3 is compared with 4. since we have not yet reached the true minimum for this round (namely, 2), this comparison will have to be done again. next 3 is compared with 2. 2 will later be determined to be the minimum value of round 0, so comparisons done later in round 0 will not be repeated. next 2 is compared with 5.

after round 0 array looks like this:
2 4 3 5
in round 2, 4 is compared with 3. this comparison was already done in round 0 as mentioned above. basically insertion sort forgets the temporary mins in each round before the true min for the round is found. and those temporary mins will later be found to be actual mins in later rounds via redundant comparision.

b)b.) mergesort is parsimonious.

well, this will be harder to explain in english because i cannot rely on a simple counterexample to demonstrate where redundant comparisons happen.

here is how mergesort works:
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 in side "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 in 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)

c.) heapsort, eh? i remember writing a function called heapify() a long time ago in a course as a helper function to heapsort, but i dont remember exactly how that algorithm works. refresh my memory, and i can tell you if it is parsimonious.

EDIT:
oh shoot. for part a), i gave the answer for selection sort, which is different than insertion sort. it appears 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 touched element is compared with already finished elements. so since every comparison is between a new element and an old one, the same comparison is never done twice.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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