Provide 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

find average runtime complexity and worst case runtime complexity .

Is above problem \"stable \" in the sense that values with same parity will not be exchanged ?

Does it remind you of selection sorting algorithm that we have studied ?if so explain any difference in average runtime complexity between the sorting algorithm and above problem?

Solution

Hi,Please find my code.

My algorithm is most optimized. It runs in O(n) time.

No. my algorithm does not use Selection Sort concept(time : O(n^2)):

Please let me know in case of any issue:

Algorithm:
arrangeEvenOdd(int arr[], int size)
   1) take two index variables left and right:
   left = 0, right = size -1
   2) Keep incrementing left index until we see an odd number.
   3) Keep decrementing right index until we see an even number.
   4) If lef < right then swap arr[left] and arr[right]

void arrangeEvenOdd(int arr[], int size)
{
/* Initialize left and right indexes */
int left = 0, right = size-1;
while (left < right)
{
/* Increment left index while we see odd at left */
while (arr[left]%2 == 1 && left < right)
left++;

/* Decrement right index while we see even at right */
while (arr[right]%2 == 0 && left < right)
right--;

if (left < right)
{
/* Swap arr[left] and arr[right]*/
int temp = arr[left];
arr[left] =arr[right];
arr[right] = temp;

left++;
right--;
}
}
}

Yes: This algorithm is stable, maintains the order of elements

Time Complexity: O(n)