CODEWITHSUNDEEP
c++sortingindexingin-place
Jilong Yin
Jilong Yin

Reputation: 330

How to do in-place sorting a list according to a given index in C++

I have a large list of objects(struct). They have been sorted and the index have been saved in another list. How to do in-place sort according to the index? For example,

FOO A[5] =[a5,a4,a8,a1,a3]
int idx[5] = [3,0,4,1,2]

expected results:

A[5] = [a1,a5,a3,a4,a8]

As the list A is very large, an in-place sorting method without additional big buffer is wanted. How can I realize this?

Thank you all.

Upvotes: 1

Views: 733

Answers (1)

kritzikratzi
kritzikratzi

Reputation: 20231

What you are looking for is called "applying a permutation" and is considered a solved problem (lucky you).

Raymond has an interesting discussion about it on his blog with an in-place solution given https://devblogs.microsoft.com/oldnewthing/20170102-00/?p=95095

I've taken the liberty to adjust his solution for arrays. You can find the original version working on vectors in his blog.

#include <iostream>

template<typename T, size_t N>
void apply_permutation(T * v, size_t * indices)
{
    using std::swap; // to permit Koenig lookup
    for (size_t i = 0; i < N; i++) {
        auto current = i;
        while (i != indices[current]) {
            auto next = indices[current];
            swap(v[current], v[next]);
            indices[current] = current;
            current = next;
        }
        indices[current] = current;
    }
}

int main(){
    const int N = 5; 
    std::string data[N] = {"a5","a4","a8","a1","a3"};
    size_t idx[N] = {3,0,4,1,2};
    apply_permutation<std::string,N>(data, idx);

    for(auto & s : data){
        std::cout << s << std::endl;
    }
}

Output:

g++ test2.cpp && ./a.exe
a1
a5
a3
a4
a8

Upvotes: 4

Related Questions