c++sorting

How to sort elements whose distance is constant?


I need to sort elements that has the same distance to each other (eg: the indicies create an arithmetic sequence)

For example, I have this std::vector

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

I only want to sort the elements with the indicies 1, 4, 7, 10, (the corresponding values is 10, 7, 4, 1). The resulting array would look like this:

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

I have written this code:

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

void sort_constant_jump(std::vector<int> &foo, int start, int jump)
{
    std::vector<int> need_to_sort;
    for(int index = start; index < foo.size(); index += jump)
    {
        need_to_sort.push_back(foo[index]);
    }

    std::sort(need_to_sort.begin(), need_to_sort.end());

    for(int index = 0; index < need_to_sort.size(); ++index)
    {
        foo[index * jump + start] = need_to_sort[index];
    }
}

int main()
{
    std::vector<int> foo {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    sort_constant_jump(foo, 1, 3);

    for(int number : foo)
        std::cout << number << ' ';
}

But it needs to copy the elements first, which is unwanted. Is there anyway to do this in-place and not creating a seperate container, sorting it and assigning the solution again?


Solution

  • For C++23 you can use stride_view, online demo : https://onlinegdb.com/WsqPcwj36

    #include <ranges>
    #include <vector>
    #include <algorithm>
    #include <iostream>
    
    int main()
    {
        std::vector<int> values{11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    
        // drop(1) to skip 1st element
        // then only sort every 3rd element
        std::ranges::sort( values | std::views::drop(1) | std::views::stride(3) );
        
        std::cout << "Expected : 11 1 9 8 4 6 5 7 3 2 10 0\n";
        std::cout << "Actual   : ";
        
        for(const auto value : values)
        {
            std::cout << value << " ";
        }
    }
    

    The output will be:

    Expected : 11 1 9 8 4 6 5 7 3 2 10 0
    Actual   : 11 1 9 8 4 6 5 7 3 2 10 0 
    
    ...Program finished with exit code 0
    Press ENTER to exit console.