Is there any way to do this?

Doing it with a separate array to hold and sort all of the evens is pretty trivial:

1. place all evens in a separate array
2. sort the array containing the evens
3. iterate through original array, replacing the even elements

But... I can't seem to find a way to do this without a separate array to hold the evens. Any tips?

CodePudding user response：

You would use any sorting algorithm and ignore the Odd ones.
Just swap values in-place without creating a new array.

for (int i = 0; i < input.length; i  )
{
    var cur = input[i];

    // ignore odd
    if (cur % 2 != 0)
        continue;

    var lowest = cur;
    var lowestIx = 0;

    // find the lowest value
    for (int j = i   1; j < input.length; j  )
    {
        var next = input[j];
        
        // ignore odd
        if (next % 2 != 0)
            continue;

        if (next < lowest)
        {
            lowestIx = j;
            lowest = next;
        }
    }

    // swap with lowest
    if (lowest != cur)
    {
        var tmp = input[lowestIx];
        input[lowestIx] = input[i];
        input[i] = tmp;
    }
}

CodePudding user response：

Sure. I'm confident many of the standard in-place search algorithms can be modified, but insertion sort is particularly easy. The usual sort:

void sort(int *a, int size) {
  for (int s = 1; s < size;   s) {
    int t = a[s], i;
    for (i = s; i > 0 && t < a[i - 1]; --i) a[i] = a[i - 1];
    a[i] = t;
  }
}

So here we do the same thing except with extra inserted loops to ignore odd entries. This is a quick hack, very possibly with bugs remaining:

void sort_evens(int *a, int size) {
  int i, s;
  for (s = 0; s < size && a[s] % 2 == 1;   s) /* skip */;
  if (s == size) return;

  while (1) {
    for (  s; s < size && a[s] % 2 == 1;   s) /* skip */;
    if (s == size) return;
    int i_last = s, t = a[s];
    for (i = s - 1; i >= 0; --i) {
      for ( ; i >= 0 && a[i] % 2 == 1; --i) /* skip */;
      if (i < 0 || t >= a[i]) break;
      a[i_last] = a[i];
      i_last = i;
    }
    a[i_last] = t;
  }
}

On this data:

int a[] = {7,3,10,9,0,1,4,3,2,1,6,8,3,5,};

it produces

7 3 0 9 2 1 4 3 6 1 8 10 3 5

More fun would be heapsort.