C++

Forum

 
Sorting two arrays of structures

Nitisha Rathi (3)
I wanted to sort two structure-arrays according to their element values and get their indices changed accordingly.For example if my array is

A[]= { 2 4 1 8 6}
indices[]={ 1 2 3 4 5}

then after sorting it should become
A[]= { 1 2 4 6 8}
indices[]={ 3 1 2 5 4}

I tried implementing it using the following code but I failed to get correct output.Somebody please help.!!

Code:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
#include<iostream>
#include<cstdio>
using namespace std;
#define inf 100000
struct array
{
    int x;
    int y;
};
void merge(struct array [],int,int,int);
void mergesort(struct array a[],int low,int high)
{
    if(low<high)
    {
       int mid=(low+high)/2;
       mergesort(a,low,mid);
       mergesort(a,mid+1,high);
       merge(a,low,mid,high);
    }
    
}
void merge(struct array a[],int low,int mid,int high)
{
    int n1,n2,i,j,k;
    n1=mid-low+1;
    n2=high-mid;
    int l[n1+1],r[n2+1],p[n1+1],q[n2+1];
    for(i=1;i<=n1;i++)
    {
        l[i]=a[low+i-1].x;
        p[i]=a[low+i-1].y;
    }
    
    for(j=1;j<=n2;j++)
    {
        r[j]=a[mid+j].x;
        q[j]=a[mid+j].y;
    }
    
    l[i+1]=inf;
    r[j+1]=inf;
    p[i+1]=inf;
    q[j+1]=inf;
    
    
    i=1;
    j=1;
    for(k=low;k<=high;k++)
    {
        if(l[i]<=r[j])
        {
            a[k].x=l[i];
            a[k].y=p[i];
            i++;
        }
        else
        {
            a[k].x=r[j];
            a[k].y=q[j];
            j++;
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int i;
        struct array b[n+1],c[n+1];
        for(i=1;i<=n;i++)
        {
            scanf("%d",&b[i].x);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&c[i].x);
        }
        for(i=1;i<=n;i++)
        {
            b[i].y=i;
            c[i].y=i;
        }
        mergesort(b,1,n);
        for(i=1;i<=n;i++)
        {
           printf("%d ",b[i].x); 
        }
        mergesort(c,1,n);
        
        printf("\n");
        for(i=1;i<=n;i++)
        {
           printf("%d ",c[i].x); 
        }
        
        
    }
    return 0;
}
Last edited on
tcs (519)
Your code is unreadable. Would you please use at least right indentation. There are also some buttons at the right of the editor field of this page. They are allowed to be used.
MiiNiPaa (8886)
You can use std::pair data type http://cplusplus.com/reference/utility/pair/ for storing values with their indexes. std::pair comes with overloaded < operator, so you might sort your array of pair<int, int> as easily as you can sort integers.
Nitisha Rathi (3)
I am sorry for that.Done the indentation.Would you please have a look now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
#include<iostream>
#include<cstdio>
using namespace std;
#define inf 100000
struct array
{
    int x;
    int y;
};
void merge(struct array [],int,int,int);
void mergesort(struct array a[],int low,int high)
{
    if(low<high)
    {
       int mid=(low+high)/2;
       mergesort(a,low,mid);
       mergesort(a,mid+1,high);
       merge(a,low,mid,high);
    }
    
}
void merge(struct array a[],int low,int mid,int high)
{
    int n1,n2,i,j,k;
    n1=mid-low+1;
    n2=high-mid;
    struct array l[n1+1],r[n2+1];
    for(i=1;i<=n1;i++)
    {
        l[i].x=a[low+i-1].x;
        l[i].y=a[low+i-1].y;
    }
    
    for(j=1;j<=n2;j++)
    {
        r[j].x=a[mid+j].x;
        r[j].y=a[mid+j].y;
    }
    
    l[i+1].x=inf;
    r[j+1].x=inf;
    
    
    i=1;
    j=1;
    for(k=low;k<=high;k++)
    {
        if(l[i].x<=r[j].x)
        {
            a[k].x=l[i].x;
            a[k].y=l[i].y;
            i++;
        }
        else
        {
            a[k].x=r[j].x;
            a[k].y=r[j].y;
            j++;
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int i;
        struct array b[n+1],c[n+1];
        for(i=1;i<=n;i++)
        {
            scanf("%d",&b[i].x);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&c[i].x);
        }
        for(i=1;i<=n;i++)
        {
            b[i].y=i;
            c[i].y=i;
        }
        mergesort(b,1,n);
        for(i=1;i<=n;i++)
        {
           printf("%d ",b[i].x); 
        }
        mergesort(c,1,n);
        
        printf("\n");
        for(i=1;i<=n;i++)
        {
           printf("%d ",c[i].x); 
        }
        
        
    }
    return 0;
}
Nitisha Rathi (3)
It worked.
Thanks :)
Topic archived. No new replies allowed.