c - odds to the first and evens last

Question

I am trying to solve a problem like ... in an array we have to move all the odd elements to the start ...and even elements to the end ... i tried this way but evens lose order here ...can someone help me ??????? the output i get is ...1 3 5 7 9 4 8 2 6
expecting an linear time in place solution ...

 #include<stdio.h>
 void swap(int *p,int *q)
 {
 *p=*p^*q;
  *q=*p^*q;
  *p=*p^*q;
 }
  int main()
  {
  int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
  int  odd=0;
  int even=0;
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  while(even< arr_size){
     if(arr[even]&1)
        swap(&arr[odd++],&arr[even++]);
     else
        even++;
  }
 int i=0;
 for(i=0;i<arr_size ;i++)
 printf("%d  ",arr[i]);
 return 0;
}

Answer 1

How about this solution

#include<stdio.h>


  int main()
  {
  int i;
  int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  int sorted[arr_size];
  int sp = 0;
  for(i=0;i<arr_size;i++){
     if(arr[i]&1){
        sorted[sp++]=arr[i];
     }
  }

  for(i=0;i<arr_size;i++){
     if(!(arr[i]&1)){
        sorted[sp++]=arr[i];
     }
  }

  for(i=0;i< arr_size ;i++)
    printf("%d  ", sorted[i]);
 return 0;
}

the output is

 1  3  5  7  9  2  4  6  8  

** UPDATE **

while the above uses more space and runs over the list twice, the following runs over the list only once, but still use more space

 int main(){

  int i;
  int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  int sorted[arr_size];
  int even = 1+arr_size/2;
  int odd  = 0;

  for(i=0;i<arr_size;i++){
     if(arr[i]&1)
        sorted[odd++]=arr[i];
     else
        sorted[even++]=arr[i];
  }

  for(i=0;i< arr_size ;i++)
    printf("%d  ", sorted[i]);

 return 0;
}