Algo_lab-codes/Merge&QuickSort.cpp at master · shaad24/Algo_lab-codes · GitHub

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
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
#define ll                  long long
#define rep(i,n)            for(ll i=0;i<n;i++)
#define hell                1000000007LL
#define vi                  vector<ll>
#define vii                 vector< vi >
#define pb                  push_back
#define mp                  make_pair
#define fi                  first
#define se                  second
#define pii                 pair<int,int>
#define all(c)              c.begin(),c.end()
#define sz(c)               c.size()
ll Max(ll a, ll b) { return a > b ? a : b; }
ll Min(ll a, ll b) { return a < b ? a : b; }
vi mergeSort(vi arr)
{
    ll n=sz(arr);
    queue< pii > q;
    rep(i,n) q.push(mp(i,i));
    while(sz(q)>1)
    {
        pii x=q.front();
        q.pop();
        pii y=q.front();
        q.pop();
        if((x.se-x.fi+1)+(y.se-y.fi+1)!=Max(x.se,y.se)-Min(x.fi,y.fi)+1)
        {
            q.push(x);
            x=y;
            y=q.front();
            q.pop();
        }
        queue<ll> xa,ya,za;
        rep(j,x.se-x.fi+1) xa.push(arr[x.fi+j]);
        rep(j,y.se-y.fi+1) ya.push(arr[y.fi+j]);
        while(!xa.empty() && !ya.empty())
        {
            za.push(Min(xa.front(),ya.front()));
            if(xa.front()<ya.front())  xa.pop();
            else ya.pop();
        }
        while(!xa.empty())
        {
            za.push(xa.front());
            xa.pop();
        }
        while(!ya.empty())
        {
            za.push(ya.front());
            ya.pop();
        }
        ll st=Min(x.fi,y.fi);
        while(!za.empty())
        {
            arr[st++]=za.front();
            za.pop();
        }
        q.push(mp(Min(x.fi,y.fi),Max(x.se,y.se)));
    }
    return arr;
}
vi quickSort(vi arr)
{
    ll n=sz(arr);
    stack< pii > s;
    s.push(mp(0,n-1));
    while(!s.empty())
    {
        pii z=s.top();
        s.pop();
        ll p=arr[z.fi],c=0;
        rep(i,z.se-z.fi) if(arr[z.fi+i+1]<=p) c++;
        swap(arr[z.fi],arr[z.fi+c]);
        ll in=z.fi+c+1;
        for(ll i=z.fi;i<z.fi+c;i++)
        {
            if(arr[i]>p)
            {
                for(ll j=in;j<=z.se;j++)
                {
                    if(arr[j]<=p)
                    {
                        swap(arr[i],arr[j]);
                        in=j+1;
                        break;
                    }
                }
            }
        }
        if(c-1>0) s.push(mp(z.fi,z.fi+c-1));
        if(z.fi+c+1<z.se) s.push(mp(z.fi+c+1,z.se));
    }
    return arr;
}
int main()
{
    ll t;
    cin>>t;
    rep(i,t)
    {
        ll n;
        cin>>n;
        vi arr(n);
        rep(j,n) cin>>arr[j];
        vi x=mergeSort(arr);
        vi y=quickSort(arr);
        rep(j,n) cout<<x[j]<<" ";
        cout<<endl;
        rep(j,n) cout<<y[j]<<" ";
        cout<<endl;
    }
    return 0;
}