How to alternate sort between even and odds ascendingly in C ?-CodePudding

I have an array of equal even and odd integers. I want to sort the array such that array would be in that pattern: even1, odd1, even2, odd2, even3, odd3,.. and so on where even1 <= even2 <= even3 and odd1 <= odd2 <= odd3.

For instance if array is [1, 2, 3, 4, 5, 6]. Sorted array would be [2, 1, 4, 3, 6, 5].

I want to do that using std::sort compare function. But unfortunately I couldn't. I believe it's impossible to do that.

bool cmp(int lhs, int rhs) {
    // couldn't write anything
}

CodePudding user response：

As mentioned in the comments, it's not possible to have your Comparator do all the work needed. So we'll just need a free function to do what's needed.

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> organize_numbers(const std::vector<int>& v) {
  std::vector<int> evens;
  std::vector<int> odds;

  // Separate evens and odds
  for (auto i : v) {
    i & 1 ? odds.push_back(i) : evens.push_back(i);
  }

  std::sort(evens.begin(), evens.end());
  std::sort(odds.begin(), odds.end());

  // Zip evens and odds back together
  std::vector<int> result;
  std::size_t i = 0;
  for (; i < evens.size() && i < odds.size();   i) {
    result.push_back(evens[i]);
    result.push_back(odds[i]);
  }

  // One of evens or odds may be longer
  auto& remainder = evens.size() > odds.size() ? evens : odds;
  for (; i < remainder.size();   i) {
    result.push_back(remainder[i]);
  }

  return result;
}

int main() {
  std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 9, 11, 13};

  nums = organize_numbers(nums);

  for (auto i : nums) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}

The function separates the odds and evens, sorts the odds and evens, and zips them back together. The thing to note is the final loop to handle the scenario where one of evens or odds is longer than the other. Move semantics make the value swapping less expensive.

I'm sure that there is a method involving std::partition to save a bit on the storage cost. You could separate the evens and odds, sort each range separately, and then swap values around. This would allow you to modify the vector in-place which might be desirable.

CodePudding user response：

First things first, I think the question needs to be improved, because it's very unclear.

However, I'll try to speculate.

I have an array of equal even and odd integers.

Based on this, since even and odd numbers can't be equal, I assume you're trying to say that you have an equal number of even and odd integers, for instance 3 odd and 3 even integers, as in the case of input [1, 2, 3, 4, 5, 6].

On the other hand, I think the example [1, 2, 3, 4, 5, 6] is not general enough, as every integer of one parity is already between two successive integers of the other parity, so the solution is to swap the first two elements, the send two elements, the third two elements and so on.

A slightly more general example would be [1, 2, 5, 3, 10, 8] which should become [2, 1, 8, 3, 10, 5].

To get that, one strategy is to

partition the vector/list/whatever such that all even numbers occupy the left part of it and all odd numbers occupy the right part of it ([2,10,8,1,5,3]),
sort the two partitions independently ([2,8,10,1,3,5]),
zip them in a range of ranges-of-2 ([[2,1],[8,3],[10,5]])
concatenate those ranges ([2,1,8,3,10,5])

You can do this easily with Range-v3, and it almost reads like the list above:

#include <iostream>
#include <range/v3/action/sort.hpp>
#include <range/v3/algorithm/partition.hpp>
#include <range/v3/view/concat.hpp>
#include <range/v3/view/drop.hpp>
#include <range/v3/view/join.hpp>
#include <range/v3/view/single.hpp>
#include <range/v3/view/take.hpp>
#include <range/v3/view/zip_with.hpp>
#include <vector>

using ranges::partition;
using namespace ranges::actions;
using namespace ranges::views;

int main(){
    std::vector<int> v{1, 2, 5, 3, 10, 8};
    auto constexpr is_even = [](int i){ return i % 2 == 0; };
    
    auto constexpr make_range_of_2 = [](int x, int y){
        return concat(single(x), single(y));
    };
    partition(v, is_even); // partition
    auto r = zip_with(make_range_of_2,
                      sort(v | take(v.size()/2)/* even integers */),
                      sort(v | drop(v.size()/2)/* odd  integers */))
             | join/* range-or-ranges -> range */;

    for (auto i : r) {
        std::cout << i << std::endl;
    }
}

Considering that half of the code is #includes and usings, the solution is pretty neat.

Let's look at it again, vs English:

we partition the collection v such that all even integers come before all odd integers,
```
partition(v, is_even); // partition
```
we zip_with the function make_range_of_2
```
auto r = zip_with(make_range_of_2,
```

the sorted range of the first half of v (the even integers)

                  sort(v | take(v.size()/2)/* even integers */),

and the sorted rage of the second half of v (the odd integers),

                  sort(v | drop(v.size()/2)/* odd  integers */))

and finally we join together all the "pairs" that we got with zip_with in one big range
```
         | join/* range-or-ranges -> range */;
```

It explains itself!

Maybe the less clear part is the implementation of make_range_of_2. What we need is a function that given two ints returns a range containing only those two. I don't know if there's a simpler way, but the first I could think of is making a 1-element range out of each int via single, and then concatenating them.

CodePudding user response：

If you create a compare function that puts all odd numbers before even and simply compares within those groups, you can in one sort have all odds sorted followed by all evens sorted.

You'd then need to swap them correctly.

Something like this

bool cmp(int lhs, int rhs) {
    if ((lhs ^ rhs) & 1) // different oddness
        return lhs & 1;  // place odds first
    return lhs < rhs;
}