Can't sort arrays with even numbers followed by odd numbers

Question

I first wrote this: (which works as expected)

#include<iostream>
using namespace std;

int main() {
    int a[5],cpy[5],ctr = 0;

    for (int i = 0 ; i<5 ; i++) {
        cout<<"Enter Value for index "<<i<<": ";
        cin>>a[i];
    }

    for (int i = 0 ; i<5 ; i++)
        if (a[i]%2==0) {
            cpy[ctr]=a[i];
            ctr++;
        }
    for (int i = 0 ; i<5 ; i++)
        if (a[i]%2!=0) {
            cpy[ctr]=a[i];
            ctr++;
        }

    for (int i = 0 ; i<5 ; i++)
        cout<<cpy[i]<<" ";

    return 0;
}

Wanted to make it more condensed/cleaner by improving my logic, this is what I came up with:

#include<iostream>
using namespace std;

int main() {
    int a[5],cpy[5],ctr = 0;

    for (int i = 0 ; i<5 ; i++) {
        cout<<"Enter Value for index "<<i<<": ";
        cin>>a[i];
    }

    for (int i = 0 ; i<5 && a[i]%2==0 ; i++,ctr++)
            cpy[ctr]=a[i];
    for (int i = 0 ; i<5 && a[i]%2!=0 ; i++,ctr++)
            cpy[ctr]=a[i];

    for (int i = 0 ; i<5 ; i++)
        cout<<cpy[i]<<" ";

    return 0;
}

Expected Result:

Enter Value for index 0: 1
Enter Value for index 1: 2
Enter Value for index 2: 3
Enter Value for index 3: 4
Enter Value for index 4: 5
2 4 1 3 5

What i get after running 2nd version:

Enter Value for index 0: 1
Enter Value for index 1: 2
Enter Value for index 2: 3
Enter Value for index 3: 4
Enter Value for index 4: 5
1 0 24 0 0

Can you suggest where I am wrong in the 2nd block of code. The first block works correctly.

`i<5 && a[i]%2==0 ;` this assumes that the numbers are already sorted before the sorting — 463035818_is_not_an_ai, Oct 14 '22 at 09:44
@463035818_is_not_a_number could you elaborate on how it assumes the numbers are already sorted? i just want array cpy to have all even numbers first and then followed by odd numbers. the odd or even numbers dont need to be sorted among themselves — spicysugar, Oct 14 '22 at 09:49
Stepping through this in your debugger of choice should clear things up quickly. Maybe add another cout or two in the loop bodys for good measure. — nick, Oct 14 '22 at 09:50
Your first loops stops at the first odd number (i.e. 1); the second stops at the first even number (i.e. 2). Then you print the indeterminate values in the next three positions. — molbdnilo, Oct 14 '22 at 09:55
Is there a reason you weren't using `std::sort` with a custom compare? — Caleth, Oct 14 '22 at 10:32
"could you elaborate on how it assumes the numbers are already sorted?" because it copies all even numbers and stops when it encounteres an odd one. This only makes sense when all even numbers are in the front of the input array already — 463035818_is_not_an_ai, Oct 14 '22 at 13:46

score 1 · Answer 1 · answered Oct 14 '22 at 10:16

1

Using ranges C++20 and stream iterators makes this quite nice:

void print(const auto& v)
{
    std::ranges::copy(v, std::ostream_iterator<int> { std::cout, ", " });
    std::cout << '\n';
}

int main()
{
    std::vector<int> v { std::istream_iterator<int> { std::cin }, {} };
    print(v);
    std::ranges::sort(v);
    print(v);
    std::ranges::sort(v, std::less<> {}, [](auto x) { return std::pair { x & 1, x }; });
    print(v);

    return 0;
}

https://godbolt.org/z/fhP51hM7s

answered Oct 14 '22 at 10:16

Marek R

32,568
6
55
140

Nice, but Isn't it enough to make the projection lambda simply: `[](auto x) { return x & 1; }` ? – wohlstad Oct 14 '22 at 10:34
@wohlstad that requires a stable sort, and a presorted input – Caleth Oct 14 '22 at 10:34
From the OP's code, it seems like they only require to group the evens before the odds. I don't see an attempt to actually sort the values in each group. I based my answer below on that). – wohlstad Oct 14 '22 at 10:47
If my understanding is correct, using `std::partition` will also be more efficient (in cases with big input) since it is linear (at least the overload I used). – wohlstad Oct 14 '22 at 10:54
`std::stable_partition` doesn't have simple linear complexity. – Marek R Oct 14 '22 at 13:15

César Debeunne · Accepted Answer · 2022-10-14T09:55:24.783

The problem here is that you will never enter the first loop. The counter is incremented only if the condition is satisfied, otherwise the loop is broken. You should not implement a condition like this.

I suggest you to try the following with std::vector :

#include<iostream>
#include<vector>
using namespace std;

int main() {
    vector<int> a, cpy;

    for (int i = 0 ; i<5 ; i++) {
        a.push_back(i+1);
    }

    for (int i = 0 ; i<5; i++) {
        if (a[i]%2 == 0)
            cpy.push_back(a.at(i));
    }
    for (int i = 0 ; i<5 ; i++) {
        if (a[i]%2 != 0)
            cpy.push_back(a.at(i));
    }

    for (int i = 0 ; i<5 ; i++)
        cout<<cpy[i]<<" ";

    return 0;
}

It works as expected, and in a more condensed manner.

wohlstad · Answer 3 · 2022-10-14T16:39:08.540

My answer assumes it is only required to group the evens before the odds, and that the internal order inside the groups does not matter (I believe it is implied by the OP's code).

In this case you can use std::partition, with a lambda function to separate even and odd values.
Also instead of using raw C arrays, better to use std::vector.

A complete example:

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

int main()
{
    std::vector<int> a = { 1,2,3,4,5 };
    std::vector<int> cpy = a;  // Create a copy. This could be avoided if you prefer

    // Partition into evens and odds:
    std::partition(cpy.begin(), cpy.end(), [](int n) {return n % 2 == 0; });

    // Print the result:
    for (int n : cpy) {
        std::cout << n << ", ";
    }
    std::cout << std::endl; 
}

Possible Output:

4, 2, 3, 1, 5,

Note that the evens are always before the odds, but internally each group's order is not guaranteed. I understood this is all that you require.

A side note:
Better to avoid using namespace std - see here Why is "using namespace std;" considered bad practice?.

score 0 · Answer 4 · answered Oct 14 '22 at 09:51

The problem is here:

 i < 5 && a[i] % 2 == 0

The first number in the a array is 1, that means for the first iteration, a[i] will be 1, and a[i] % 2 == 0 will be false, and thus will break the loop.

The first loop has never been executed for this reason, and the second loop is only executed once.

Those numbers 0 24 0 0 you see in the result are just garbage values in your memory since only 1 number is actually written into the cpy array. You can fire up the debugger or simply print out ctr and it will be 1.

Can't sort arrays with even numbers followed by odd numbers

4 Answers4