How can I sort only some parts of the array in a specific order in c++?

Question

So let's assume I have an array array{12, 10, 10, 9, 8, 8, 8} in descending order. I want to sort the numbers that can be divided by 2 but not with 4 in ascending order at the end of the array, the numbers that are divided by 4 sorted at the start of the array in descending order and the rest in the middle(no specific order). For my example, after the transformation it should look something like this: array{12, 8, 8, 8, 9, 10, 10}. Is there any way I can do this efficiently? c++ language. Sorry for any misspelling.

Answer 1

Let's organize the requirement.

The required order is:

1. Numbers that are divided by 4
2. Others
3. Numbers that can be divided by 2 but not with 4

Among the numbers with same priority according to the above rule, the numbers should be

1. Descending order
2. No specific order
3. Ascending order

Let's implement this:

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

void test(std::vector<int> array) { // intensionally passed by value
    std::cout << "before sorting:";
    for (int v : array) std::cout << ' ' << v;
    std::cout << '\n';

    std::sort(array.begin(), array.end(), [](int a, int b) -> bool {
        int pa, pb; // priority a/b

        if (a % 4 == 0) pa = 1;
        else if (a % 2 == 0) pa = 3;
        else pa = 2;

        if (b % 4 == 0) pb = 1;
        else if (b % 2 == 0) pb = 3;
        else pb = 2;

        // if the priority differs, sort according to the priority
        if (pa != pb) return pa < pb;
        // if both can be divided by 4, sort in descending order
        if (pa == 1) return b < a;
        // if both can be divided by 2 but not with 4, sort in ascending order
        if (pa == 3) return a < b;
        // no specific order for the rest
        return false;
    });

    std::cout << "after  sorting:";
    for (int v : array) std::cout << ' ' << v;
    std::cout << '\n';
}

int main(void) {
    std::vector<int> array = {12, 10, 10, 9, 8, 8, 8};
    std::vector<int> array2 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    test(array);
    std::cout << '\n';
    test(array2);
    return 0;
}

Example output:

before sorting: 12 10 10 9 8 8 8
after  sorting: 12 8 8 8 9 10 10

before sorting: 10 9 8 7 6 5 4 3 2 1
after  sorting: 8 4 9 7 5 3 1 2 6 10

Answer 2

As an alternative to MikeCAT's fine answer, C++20 adds a variation of sort which accepts a projection, i.e. a function to apply to each element before we pass it to the comparison functor.

This utilises the fact that std::tuple has a predefined < that orders the tuple by each member in turn.

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

std::tuple<int, int> my_order(int val) {
    if (val % 4 == 0) return { 1, -val };
    else if (val % 2 == 0) return { 3, val };
    else return { 2, 0 };
}

void test(std::vector<int> array) { // intensionally passed by value
    std::cout << "before sorting:";
    for (int v : array) std::cout << ' ' << v;
    std::cout << '\n';

    std::ranges::sort(array.begin(), array.end(), std::ranges::less{}, my_order);

    std::cout << "after  sorting:";
    for (int v : array) std::cout << ' ' << v;
    std::cout << '\n';
}

int main(void) {
    std::vector<int> array = {12, 10, 10, 9, 8, 8, 8};
    std::vector<int> array2 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    test(array);
    std::cout << '\n';
    test(array2);
    return 0;
}