How can I use sort() function in C++ doing something together?

Question

I have two arrays as

(i) arrStart[]={0 1 3 5 6 8 10 12 15};
(ii) arrEnd[]={4 2 7 11 16 9 14 13 17};

I want to sort arrEnd[] such that corresponding integer in arrStart[] also get swapped matching with integer of arrEnd[] like

Output:

(i) arrStart[]={1 0 3 8 5 12 10 6 15};
(ii) arrEnd[]={2 4 7 9 11 13 14 16 17};

I am using

sort(arrEnd,arrEnd+8);

Is there any logic to get above output such that i could get rid of writing complete sorting algorithm?

You don't need to rewrite the sorting algorithm: just associate the arrStart data with arrEnd data. For example, **arrEnd[x] = arrEnd[x] * 100 + arrStart[x]** — cup, Nov 11 '15 at 05:53
Thanks @cup Your solution worked.It required some data manipulation but anyhow worked.. — nitish, Nov 11 '15 at 06:21

rcgldr · Accepted Answer · 2015-11-11T06:30:44.917

Method 1: Create an array of indices 0 to n-1; Use sort with a lambda compare to compare arrEnd[] elements. Then use the sorted indices to reorder both arrays according to the array of sorted indices.

Method 2: Create an array of pointers to arrEnd[] elements, then sort the array of pointers using a compare function. The compare function only needs to know the type of the elements. Then reorder both arrays according to the array of sorted pointers.

Example for method 2. Reorder in place time complexity is linear, O(n).

bool compare(const int *p0, const int *p1)
{
    return *p0 < *p1;
}

int main()
{
int a[8] = {7,5,0,6,4,2,3,1};
char b[8] = {'h','f','a','g','e','c','d','b'};
int *pa[8];
size_t i, j, k;
int ta;
char tb;
    // create array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];
    // sort array of pointers to a[]
    std::sort(pa, pa+sizeof(a)/sizeof(a[0]), compare);
    // reorder a[] and b[] according to the array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            tb = b[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                b[k] = b[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            b[k] = tb;
            pa[k] = &a[k];
        }
    }
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        std::cout << a[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
        std::cout << b[i] << ' ';
    std::cout << std::endl;
    return 0;
}

How can I use sort() function in C++ doing something together?

1 Answers1