Develop an efficient in-place algorithm called Partition-Even-Odd(A) that partit
ID: 3843664 • Letter: D
Question
Develop an efficient in-place algorithm called Partition-Even-Odd(A) that partitions an array A in even and odd numbers. The algorithm must terminate with A containing all its even elements preceding all its odd elements. For example, for input A = 7, 17, 74, 21, 7, 9, 26, 10, the result might be A = 74, 10, 26, 17, 7, 21, 9, 7 .
Partition-Even-Odd must be an in-place algorithm, which means that it may use only a constant memory space in addition to A. In practice, this means that you may not use another temporary array.
i) Write the pseudo-code for Partition-Even-Odd.
ii) Characterize the complexity of Partition-Even-Odd. Briefly justify your answer.
iii) If the complexity of your algorithm is not already linear in the size of the array, write a new algorithm Partition-Even-Odd-Optimal with complexity O(N) (with N = |A|).
Explanation / Answer
The algorithm is as follows:
1.Start traversing the array from the begining and the end.
2.If traversing from the begining , encountered an odd element, stop traversing
3.If traversing from the end, encountered a even element,stop traversing
4.Swap the two elemts and again start traversing
5.Processing ends when both the traversings meet
Pseudo code is as follows:
forward_traversing = 1
backward_traversing = 1
while (lo ! = hi) { //lo = 0 and hi = size of the array - 1
if (array[lo] is even && forward_traversing == 1){
lo = lo + 1
else
forward_traversing = 0
if (array[hi] is odd && backward_traversing == 1){
lo = lo + 1
else
backward_traversing = 0
if (forward_traversing == 0 && backward_traversing == 0)
temp = array[lo]
array[lo] = array[hi]
array[hi] = temp
lo = lo+1
hi = hi -1
forward_traversing = 1
backward_traversing = 1
}
}
We have to travesre through all the elemnts once and ocassional swap operation(of constant time) needs to be performed(if required) so the complexity is of the O{n}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.