How to sort one array and get corresponding second array in C++?

Question

I have two arrays in same size. And want to sort one of the array normally and then sort the next array elements accordingly. Let's say we have two arrays

e[] = {4,2,3,7,6,8}
s[] = {2,0,4,3,7,9}

First I want to sort array e normally, Then change the element positions of s array according to the changed element positions of e.

This should be the final result

e[] = {2,3,4,6,7,8}
s[] = {0,4,2,7,3,9}

How should I do this? Should I use a class object with these two as private members and then proceed? If so, how to do that?

Answer 1

Create a single array (or vector) of std::pair objects, where first is from the first array and second from the second. Then just use std::sort with a custom comparator function that uses only second from the pair for comparison. Iterate over the sorted array (or vector) and split up into the original arrays.

Note: If the values in each array are tightly coupled then consider putting them in a structure or class instead of using two (or more) distinct arrays.

Answer 2

• What I think is use std::map
• Assign array e element as the key
• And corresponding array s element as the value.
• Then sort the may by key
• Go trough the map and get the values one by one

Answer 3

If you do this in a class, you can create an array of indices and sort the indices according to the values in e[]. If not doing this within a class, and for a more general approach, create an array of pointers to e[], then sort the pointers according to e[]. Then reorder e[] and s[] according to the pointers, converting the the sorted pointers to an index by using array_of_pointers[i] - &e[0] (or just array_of_pointers[i]-e). You could write your own sort, or use qsort, std::sort, or std::stable sort to sort the array of pointers, with a compare function that compares using dereferenced pointers (compares the values pointed to). Example C code using qsort and reorder in place logic with O(n) time complexity:

int compare(const void *pp0, const void *pp1)
{
    int i0 = **(int **)pp0;
    int i1 = **(int **)pp1;
    if(i0 > i1)return -1;
    if(i0 < i1)return  1;
    return 0;
}

int main()
{
int e[...];
int s[...];
int *pe[...];
size_t i, j, k;
int te, ts;
    /* ... */
    /* create array of pointers to e[] */
    for(i = 0; i < sizeof(e)/sizeof(e[0]); i++)
        pe[i] = &e[i];
    /* sort array of pointers */
    qsort(pe, sizeof(e)/sizeof(e[0]), sizeof(pe[0]), compare);
    /* reorder e[] and s[] according to the array of pointers */
    for(i = 0; i < sizeof(e)/sizeof(e[0]); i++){
        if(i != pe[i]-e){
            te = e[i];
            ts = s[i];
            k = i;
            while(i != (j = pe[k]-e)){
                e[k] = e[j];
                s[k] = s[j];
                pe[k] = &e[k];
                k = j;
            }
            e[k] = te;
            s[k] = ts;
            pe[k] = &e[k];
        }
    }
    /* ... */
    return 0;
}

Answer 4

If you don't want to use other Data structures and stick with the two different integer arrays..

Following code snippet will help you

int _tmain(int argc, _TCHAR* argv[])
{

    int e[] = {4,2,3,7,6,8} ;
    int s[] = {2,0,4,3,7,9} ;
    int temp ;

    int Array_Size = 6 ; // don't use hard coded value here, rather calculate from array size

    for(int i = 0 ; i < Array_Size ; i++)
    {
        for(int j = i+1 ; j < Array_Size ; j++)
        {
            if(e[i] > e[j])
            {
                // Swap elements in first array
                temp = e[j] ;
                e[j] = e[i] ;
                e[i] = temp ;

                // As you want both arrays in sync 
                // Swap elements in second array here itself
                temp = s[j] ;
                s[j] = s[i] ;
                s[i] = temp ;
            }
        }
    }

    return 0;
}

Answer 5

It is quite simple when we use structure.Your basic task is to sort two arrays. I want to suggest one method regarding it. Use a structure having two variables x and y which are used here for two arrays. Make two array of objects of this structure.

  struct Point
        {
         int x,y;
        };
  struct Point arr[n];

After providing entries to the array of structure objects, make use of STL function

sort(arr,arr+n,myfun);

where myfun is function to sort according to ur need and it is defined as

bool myfun(struct Point a,struct Point b)
{
  if(a.x<b.x)
    return true;
  else
    return false;
}

And here is the complete program in c++

#include <bits/stdc++.h>
using namespace std;
struct Point{
             int x,y;
            };
bool myfun(struct Point a,struct Point b)
{
  if(a.x<b.x)
      return true;
  else
      return false;
}
int main()
{
    int n;  //n is the number of elements of array
    cin>>n;
    struct Point arr[n];
    //Enter first array
    for(int i=0;i<n;i++)
        cin>>arr[i].x;
    //Enter second array
    for(int i=0;i<n;i++)
        cin>>arr[i].y;
    //sorting with the help of myfun
    sort(arr,arr+n,myfun);
    //now print the arrays
    for(int i=0;i<n;i++)
        cout<<arr[i].x<<" ";
    cout<<"\n";
    for(int i=0;i<n;i++)
        cout<<arr[i].y<<" ";
    return 0;
}

Answer 6

void bubbleSort(int e[], int s[], int n) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - j; i++) {
                  if (e[i] > e[i + 1]) {
                        tmp = e[i];
                        e[i] = e[i + 1];
                        e[i + 1] = tmp;
                        tmp = s[i];
                        s[i] = s[i + 1];
                        s[i + 1] = tmp;

                        swapped = true;
                  }
            }
      }
}