Sort array, pair numbers first in C

Question

I'm trying to sort an array of ints, even numbers first and then odd numbers.

Say I have Array[10]={2,4,3,11,0,12,88,99,111,-15}.

I want it to end up like this: 0, 2, 4, 12, 88, -15, 3, 11, 99, 111

for(i = 0 ; i < 10 ; i++) {
  for(j = 0 ; j < 10 ; j++) {
    if(Array[i] % 2 != 0) {
      Array[j] = Array[i];
    }
  }
}

I'm lost. I have no idea how to proceed beyond that.

once you have a simple sort, how could you push the first odd value all the way to the end of the array? — john elemans, Nov 26 '15 at 19:57
do you mean even numbers first, then odd numbers ? i don't see any pairs — AndersK, Nov 26 '15 at 20:03
yes I'm sorry, I meant even numbers first then odd numbers. I'm french. — Cpotmeha, Nov 26 '15 at 20:07
Your example doesn't make much sense. And `4` disappeared in the expected result. You need to describe the "sorting" process you are expecting. — dda, Nov 26 '15 at 20:07

score 2 · Answer 1 · answered Nov 26 '15 at 20:04

2

Take any sort algorithm but use a special comparison : a even number should considered as lesser than a odd one, and if two numbers have the same parity then use standard comparison. Something like:

lessthan(a,b):
  if (a%2==b%2)  // same parity
    return a<b   // then is a < b ?
  else
    return a%2==0 // else, is a even ?

answered Nov 26 '15 at 20:04

Jean-Baptiste Yunès

34,548
4
48
69

a C sort would usually return `a - b` to sort numbers, not `a < b` – Alnitak Nov 26 '15 at 20:32
@Alnitak Subtracting values is always a mistake when sorting integers with qsort. – this Nov 26 '15 at 20:36
@this overflow? right - google suggests yes - good point. In an event, my point stands that idiomatic C sort functions use -1, 0, 1, not a < test – Alnitak Nov 26 '15 at 20:38
@Alnitak Yes. Undefined for signed values. For unsigned wraps and gives incorrect results. – this Nov 26 '15 at 20:41
OP wants to implements his own sorting, not to use a `*sort` function, so from an algorithmic point of view, he just needs a boolean comparator. – Jean-Baptiste Yunès Nov 26 '15 at 20:43
I don't think this algorithm is _quite_ correct (in the second branch) – Alnitak Nov 26 '15 at 20:47
@Alnitak It is clearly pseudo code. OP can figure out the details. – this Nov 26 '15 at 20:49
@Alnitak If parity is different then if a is even it is the minimum, isn't it? – Jean-Baptiste Yunès Nov 26 '15 at 20:49
Right - I figured out the problem - with negative numbers in C, `n % 2` is 0 or -1, not 0 or 1, so comparing e.g. -15 % 2 with 9 % 2 will fail, incorrectly. Also, I think you may have the major/minor sort orders the wrong way around. – Alnitak Nov 26 '15 at 20:58
OK, your sort orders are actually correct, but the slightly inverted logic is non-intuitive. When comparing multiple fields in my experience it's more common for the first branch to be a `!=` test, where the branch returns the result of comparing on the major sort term, and then the fallthrough branch (when parity is the same in this case) then performs the minor sort test (i.e. a < b). This version puts the minor comparison first. – Alnitak Nov 26 '15 at 23:13

August Karlstrom · Answer 2 · 2015-11-27T07:33:00.790

Here is a solution using the standard library function qsort. Hope this helps.

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

#define LEN(arr) (sizeof (arr) / sizeof (arr)[0])

static int Odd(int n)
{
    return n % 2 != 0;
}


static int Order(const void *xPtr, const void *yPtr)
{
    int x, y, result;

    x = *((int *) xPtr);
    y = *((int *) yPtr);

    if (! Odd(x) && Odd(y)) {
        result = -1;
    } else if (Odd(x) && ! Odd(y)) {
        result = 1;
    } else if (x < y) {
        result = -1;
    } else if (x > y) {
        result = 1;
    } else {
        result = 0;
    }
    return result;
}


int main(void)
{
    int a[] = {2, 4, 3, 11, 0, 12, 88, 99, 111, -15};
    int i;

    qsort(a, LEN(a), sizeof a[0], Order);

    for (i = 0; i < LEN(a); i++) {
        printf("%d\n", a[i]);
    }

    return 0;
}

dda · Answer 3 · 2015-11-26T20:28:21.253

Do a first pass separating numbers into odd and even numbers. You now have two arrays. Sort them, them reassemble the two arrays into one.

void sort(int *, int);

int main() {
  int Array[10]={2,4,3,11,0,12,88,99,111,-15};
  int i, n=0, k=0, x=0, y=0;
  for(i=0;i<10;i++) {
    if(Array[i]%2==0) {
      n++;
    } else {
      k++;
    }
  }
  int ArrEven[n], ArrOdd[k];
  for(i=0;i<10;i++) {
    if(Array[i]%2==0) {
      ArrEven[x++]=Array[i];
    } else {
      ArrOdd[y++]=Array[i];
    }
  }
  sort(ArrEven, n);
  sort(ArrOdd, k);
  x=0;
  for(i=0;i<n;i++) {
    Array[i]=ArrEven[i];
  }
  for(i=0;i<k;i++) {
    Array[i+n]=ArrOdd[i];
  }

  for(i=0;i<10;i++) {
    printf("%d\n", Array[i]);
  }
  return 0;
}

void sort(int *array, int n) {
  for (int c = 0 ; c < ( n - 1 ); c++) {
    for (int d = 0 ; d < n - c - 1; d++) {
      if (array[d] > array[d+1]) {
        int swap = array[d];
        array[d] = array[d+1];
        array[d+1] = swap;
      }
    }
  }
}

To separate odd and even numbers. Easiest way. See code. – dda Nov 26 '15 at 20:29 — dda, Nov 26 '15 at 20:29
You can do it in the same array. – HelloWorld123456789 Nov 26 '15 at 20:29 — HelloWorld123456789, Nov 26 '15 at 20:29
Why don't you put up your answer then? – dda Nov 26 '15 at 20:30 — dda, Nov 26 '15 at 20:30

Alnitak · Answer 4 · 2015-11-26T21:00:30.093

You can make use of C's standard qsort function, but provide a custom comparator [indirectly based on Jean-Baptiste's answer]:

int evenoddsort(const void *a, const void *b) {
    int ai = *(const int *)a;
    int bi = *(const int *)b;
    int ar = abs(ai % 2);
    int br = abs(bi % 2);

    if (ar != br) {
        return ar - br;  /* even is "less than" odd */
    } else {
        return (ai < bi) ? -1 : (ai > bi) ? 1 : 0;
    }
}

usage:

qsort(Array, 10, sizeof(int), evenoddsort);

Sort array, pair numbers first in C

4 Answers4