Homework SourseProvide pseudo code for an in place no extra storage algorit
Provide pseudo code for an in place (no extra storage )algorithms to take an array of n integers and rearrange it such that all of odd numbers occurs before any of the even number and also find average worst case complexity .
Is above problem \"stable \" in the sense that values with same parity will not be exchanged ?
Does it remind you of any sorting algorithm that we have studied ?if so explain any difference in average runtime complexity between the sorting algorithm and above problem?
Provide pseudo code for an in place (no extra storage )algorithms to take an array of n integers and rearrange it such that all of odd numbers occurs before any of the even number and also find average worst case complexity .
Is above problem \"stable \" in the sense that values with same parity will not be exchanged ?
Does it remind you of any sorting algorithm that we have studied ?if so explain any difference in average runtime complexity between the sorting algorithm and above problem?
Is above problem \"stable \" in the sense that values with same parity will not be exchanged ?
Does it remind you of any sorting algorithm that we have studied ?if so explain any difference in average runtime complexity between the sorting algorithm and above problem?
Solution
Algorithm: OddsBeforeEvens(Array[1..n])
for i = 1 to n:
changed = false
for j = 1 to n:
if Array[j] %2 == 0 and Array[j+1] % 2 != 0 //If the even number is before an odd number.
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
changed = true;
if changed == false:
break;
The worst case running time complexity is: O(n2).
Yes. The algorithm is stable.
Yes. It reminds the BUBBLE sort algorithm that we have studied. The average runtime complexity for this algorithm is the same as that of bubble sort algorithm theoretically. But in practical, this algorithm is more efficient comparitively. This is because, exchanges only happen when an even number encounters before an odd one.
