Prove that the MinMaxSort algorithm below is not a correct sorting algorithm. No

Question

Prove that the MinMaxSort algorithm below is not a correct sorting algorithm. Note that the input size must be even. Input: data: array of integers Input: n: length of data, which must be even Output: a permutation of data so that data[1] lessthanorequalto data[2] lessthanorequalto ... lessthanorequalto data[n] Algorithm: MinMaxSort if n lessthanorequalto 1 then | return data end min = Array(n/2) max = Array(n/2) for i = 1 to n/2 do | mm [i] = min { data [2i - 1], data [2i] } max[i| = max {data [2i - 1], data [2i] } end return the concatenation of min and max

Explanation / Answer

Lets try the algortihm for
array a[2,8,6,5]
n = 4;

Line 2, checks if n<=1, which is not correct

Now at line 5 and 6 we create min and max arrays of 2 elements each.

starting from line 7,
i = 1 to n/2 means 1 to 2

i = 1,
min[1] = min{a[1], a[2]} = 2
max[1] = max{a[1], a[2]} = 8

i = 2,
min[2] = min{a[3], a[4]} = 5
max[2] = max{a[3], a[4]} = 6

So now, min = [2,5], max = [8,6]

The output of the algorithm is concatenation of min and max, which will be
[2,5,8,6],

we can see that 8 is greater than 6, which is not acceptable as per given condition that, the output array should be in ascending order...

===================
The problem here is that in each of the pair, we are segregating the min and max number, but the numbers in min and max can itself come in random order, as shown above.. in which case, the concatenation will fail to deliver the correct results.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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