Sort array in specific way

Question

Hello i've tried to sort array in this special case

a) Odd numbers which are divisible by 3 must come first ascendingly

b) Even numbers which are divisible by 3 must come last descendingly

c) Numbers which are not divisible by 3 are sorted ascendingly

this is my code

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

bool cmp(int b,int a){

    if((b%2 && b%3==0) && (a%2==0 || a%3 || b>a) )
        return true ;

    if((a%2==0 && a%3==0) && (b%2 || b%3) )
        return true ;

    return false ;
}

int main(){

int ar[8]={18 ,5 ,24 ,9 ,12 ,6 ,2, 3};

sort(ar,ar+8,cmp);

for(int i=0;i<8;i++)
    cout<<ar[i]<<endl ;

return 0;
}

my output

9 3 5 2 18 24 12 6

Excepted

3 9 2 5 24 18 12 6

so now the array is dvided to 3 blocks but not sorted as the special case i mentioned above

Answer 1

I would construct a tuple for that {partition1, partition2, order}:

auto helper(int i)
{
    bool isEven = i % 2 == 0;
    bool isMul3 = i % 3 == 0;
    return std::make_tuple(!(!isEven && isMul3), // partition 1
                           isEven && isMul3,     // partition2
                           isEven && isMul3 ? -i : i); // order
}

bool cmp(int lhs, int rhs){
    return helper(lhs) < helper(rhs);
}

Demo

Answer 2

This simple comparison function works for me:

bool cmp(int lhs, int rhs){
    bool lhs_div_3 = lhs % 3 == 0;
    bool rhs_div_3 = rhs % 3 == 0;
    bool lhs_odd = lhs & 1;
    bool rhs_odd = rhs & 1;

    if (lhs_div_3 && lhs_odd) // lhs in class a)
        if (rhs_div_3 && rhs_odd)
            return lhs < rhs;
        else 
            return true;

    if (!lhs_div_3) // lhs in class c)
        if (!rhs_div_3)
            return lhs < rhs;
        else
            return !rhs_odd;

    // else lhs in class b) 
    if (rhs_div_3 && !rhs_odd)
        return rhs < lhs;

    return false;
}

But if you have large arrays and care about performance, you should likely partition data first and then sort each 3 parts independently as recommended by others (to avoid such a complex, i.e., slow comparison function).

Answer 3

Using std::partition to first "split" your array into three partitions, and then sorting each partition, you will get something like

#include <iostream>
#include <array>
#include <algorithm>
#include <functional>

int main()
{
    std::array<int, 8> array = {{ 18 ,5 ,24 ,9 ,12 ,6 ,2, 3 }};

    std::cout << "Before first partitioning: ";
    for (auto const value : array)
        std::cout << value << ' ';
    std::cout << '\n';

    // First partition putting all odd number even divisible by three first
    auto second_start = std::partition(std::begin(array), std::end(array), [](int const& value) {
        return (value % 2 != 0 && value % 3 == 0);
    });

    std::cout << "Before second partitioning: ";
    for (auto const value : array)
        std::cout << value << ' ';
    std::cout << '\n';

    // Then partition putting all even number even divisible by three first
    auto third_start = std::partition(second_start, std::end(array), [](int const& value) {
        return !(value % 2 == 0 && value % 3 == 0);
    });

    std::cout << "Before sorting: ";
    for (auto const value : array)
        std::cout << value << ' ';
    std::cout << '\n';

    std::sort(std::begin(array), second_start, std::less<int>());
    std::sort(second_start, third_start, std::less<int>());
    std::sort(third_start, std::end(array), std::greater<int>());

    std::cout << "After sorting: ";
    for (auto const value : array)
        std::cout << value << ' ';
    std::cout << '\n';
}

Output

Before first partitioning: 18 5 24 9 12 6 2 3 
Before second partitioning: 3 9 24 5 12 6 2 18 
Before sorting: 3 9 2 5 12 6 24 18 
After sorting: 3 9 2 5 24 18 12 6 

The output after soring is as what you expect.

See here for it in "action".

It is more work, but is also guaranteed to behave as expected.

Answer 4

Since your comparison function is quite complex, I've rewritten it very verbosely, so each possible case can be inspected separately. I've also separated into a different function the decision about which partition of the output each element goes into.

#include <algorithm>
#include <iostream>
#include <iterator>

int classify(int const i)
{
    if (i%3==0 && i%2!=0) {
        return 1;
    }
    else if (i%3!=0) {
        return 2;
    }
    else {
        return 3;
    }
}

bool comp(int const a, int const b)
{
    int const a_part = classify(a);
    int const b_part = classify(b);

    if (a_part==1) {
        if (b_part==1) {
            // both in first partition, order ascending
            return a<b;
        }
        else {
            // a in first partition, b not, so a always first
            return true;
        }
    }
    else if (a_part==2) {
        if (b_part==1) {
            // b comes before a
            return false;
        }
        else if (b_part==2) {
            // both in middle partition, order ascendingly
            return a<b;
        }
        else {
            // a in middle partition, b in last partition, so a always first
            return true;
        }
    }
    else { // (a_part==3)
        if (b_part!=3) {
            // a in last partition, b in first or middle partition,
            // so b always comes first
            return false;
        }
        else {
            // both in last partition, order descending
            return b<a;
        }
    }

}

int main()
{
    int ar[8] = {18 ,5 ,24 ,9 ,12 ,6 ,2, 3};
    std::sort(std::begin(ar),
              std::end(ar),
              comp);
    std::copy(std::begin(ar),
              std::end(ar),
              std::ostream_iterator<int>(std::cout,
                                         "\n"));
}

Output:

$ ./SO 
3
9
2
5
24
18
12
6

Bear in mind your comparator must induce a Strict Weak Ordering, which I think this does, but it's a bit trickier than one would normally use for sorting.

Always write your code as clearly as possible, not as short as possible. If you have some complicated logic, break it up, move parts out into functions, and add plenty of comments. Remember, other people have to read and understand it, including yourself in 6 months.

---

What might be a better approach is to split the sort up. You are really talking about splitting the array into 3 partitions, each being treated differently. So use std::partition twice, and std::sort three times. I think that may well be more understandable. This code has the exact same output as the above:

bool isOddMultipleOfThree(int const i)
{
    return (i%3==0 && i%2!=0);
}

bool isEvenMultipleOfThree(int const i)
{
    return (i%3==0 && i%2==0);
}

int main()
{
    int ar[8] = {18 ,5 ,24 ,9 ,12 ,6 ,2, 3};

    // split off the first partition
    auto firstSplit = std::partition(std::begin(ar),
                                     std::end(ar),
                                     isOddMultipleOfThree);
    // sort the first partition
    std::sort(std::begin(ar),
              firstSplit,
              std::less<int>());

    // split off end partition
    // use a lambda to invert the predicate, because we want the matching
    // values pushed to the end
    auto secondSplit = std::partition(firstSplit,
                                      std::end(ar),
                                      [](int const i) {
                                        return !isEvenMultipleOfThree(i);
                                      });

    // sort middle partition
    std::sort(firstSplit,
              secondSplit,
              std::less<int>());
    // sort last partition
    std::sort(secondSplit,
              std::end(ar),
              std::greater<int>());

    // print
    std::copy(std::begin(ar),
              std::end(ar),
              std::ostream_iterator<int>(std::cout,
                                         "\n"));
}

---

Also worth mentioning, many people (myself included) consider using namespace std; and std::endl are bad practices.