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;
}

do you want odd or even at the end? and do you want the odd and evans to be sorted? — Ionut Hulub, Sep 29 '12 at 06:12
so you said the output you get is 1 3 5 7 9 4 8 2 6 . what's the problem with that/ — Ionut Hulub, Sep 29 '12 at 06:15
@IonutHulub: The ordering of the evens is lost (`4826` instead of `2468`). — Blender, Sep 29 '12 at 06:16
so in the original array the ordder of evens is 2,4,6,8,9, the order need to be maintained ... — Sree Ram, Sep 29 '12 at 06:17
Judging from the comments you left on some of the answers, it looks like you are asking for a stable, in place, single pass method to separate the odd and even numbers. Unfortunately, I don't think such a method exists. I think the answer from @HussainAl-Mutawa is about as good as you are going to get: 2 passes and `O(n)` space overhead. You can do it in one pass if you use a linked list but you still have the space overhead, and it will probably be slower than 2 passes of an array anyway. — verdesmarald, Sep 29 '12 at 09:11

halex · Answer 1 · 2012-09-29T12:06:03.963

2

You can use a call to qsort with a special compare function:

#include <stdio.h>
#include <stdlib.h>

int cmp(const void * a, const void * b) {
    int aa = *((int*)a);
    int bb = *((int*)b);
    // If aa is odd and bb is even aa is smaller
    if(aa%2 == 1 && bb%2 == 0)
        return -1;
    // If bb is odd and aa is even bb is smaller
    if(aa%2 == 0 && bb%2 == 1)
        return 1;
    // If both even or odd respect current position. (If a is before b in arr a has lower address)
    if(a<b)
        return -1;
    return 1;
}
int main(void) {
    int arr[] = { 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};    
    int len = sizeof(arr)/sizeof(arr[0]);
    int i;
    qsort(arr, len, sizeof(int), cmp);
    for(i=0; i<len; i++)
        printf("%d ", arr[i]);
    return 0;
}

For an solution that uses no auxiliary array (as HussainAl-Mutawa's does) you could use a kind of insertion sort to have an in-place solution but its runtime grows quadratic so HussainAl-Mutawa's version seems to be the optimum if runtime is preferred:). Just for completeness here my implementation:

int main(void) {
    int arr[]={ 2, 1 ,4 ,3 ,6 ,5 ,8 ,7 ,9};
    int len = sizeof(arr)/sizeof(arr[0]);
    int i,j;
    for(i=1; i<len; i++) {
        int cur=arr[i];
        if(cur%2 == 0)
            continue;
        j=i;
        while(j>0 && arr[j-1]%2 == 0) {
           arr[j]=arr[j-1];
           j--;
        }
        arr[j]=cur;
    }

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

    return 0;
}

edited Sep 29 '12 at 12:06

answered Sep 29 '12 at 06:37

halex

16,253
5
58
67

1

Unfortunately this doesn't work. `qsort` is not a stable sort, and adding the pointer comparison at the end is not sufficient to make it so. See [this question](http://stackoverflow.com/questions/584683/stabilizing-the-standard-library-qsort) for more explanation. – verdesmarald Sep 29 '12 at 07:22
@SreeRam I can't explain how it works because it doesn't work! ;) The question I linked has a good explanation of why it doesn't, what part didn't you understand? – verdesmarald Sep 29 '12 at 09:08
@verdesmarald ok u provided the comparator function ...but doent quicksort work on the basis of partitions ...(let say no duplicates which brings doesnt bring stability into picture..) – Sree Ram Sep 29 '12 at 09:35
I'm not sure what you are getting at. Keep in mind that "duplicates" in the context of stable sorting means "elements that compare equal", so in your case 2 and 4 are duplicates because they are both even. In your case an array with "no duplicates" could only contain up to two elements, one odd and one even. – verdesmarald Sep 29 '12 at 09:44
@verdesmarald `qsort` not being stable was the first problem I thought of, but nevertheless out of curiosity I tried to achieve a solution with qsort with the pointer comparing :). I tried my code with some testcases and compilers and it worked with all, so I thought there will be no problem. Could you please give me a testcase (and which compiler you used) where my code does break the order of the problem's needs? – halex Sep 29 '12 at 11:14
Sorting `{1, 2, ..., 10}` using gcc 4.3.4 (under cygwin) gives me `1, 9, 3, 7, 5, 6, 4, 8, 2, 10` instead of `1, 3, 5, 7, 9, 2, 4, 6, 8, 10`. – verdesmarald Sep 29 '12 at 13:58
@verdesmarald Thank you for alluding me to this. I only tried it on my Linux System, where it worked just fine :). – halex Sep 29 '12 at 17:08

user1406062 · Accepted Answer · 2012-09-29T11:24:32.447

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;
}

@SreeRam If you wanted an in place, single pass solution you should have said so in your question. — verdesmarald, Sep 29 '12 at 07:58
@verdesmarald sry ...should have made it more clear about my requirements ...tnks for the comment ... — Sree Ram, Sep 29 '12 at 08:14
I don't know any other way except using linked lists / queue — user1406062, Sep 29 '12 at 09:11

score -1 · Answer 3 · answered Sep 29 '12 at 06:21

if swaping is not compalsary than for this you can simply create two for loops one for adding evens and another for odds. Something like this:-

  j=0;
  for(i=2;i<a_size;i+2)
  {
     b[j++]=a[i];
  }
  for(i=1;i<a_size;i+2)
  {
     b[j++]=a[i];
  }

and in last print a.

odds to the first and evens last

3 Answers3

Related