Algorithms/Quick Sort.cpp at master · rofi93/Algorithms · 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
116
117
118
119
120
121
122
/* -------------------------------- */
/* Name: MD. Khairul Basar */
/* Institute: HSTU */
/* Dept: CSE */
/* Email: khairul.basar93@gmail.com */
/* -------------------------------- */

#include<bits/stdc++.h>
/* all header files included */

#definefs first
#definesc second
#definespprintf("")
#definenlprintf("\n")
#definepb(a) push_back(a)
#definemp(a,b) make_pair(a,b)

#definesetzero(a) memset(a,0,sizeof(a))
#definesetneg(a) memset(a,-1,sizeof(a))
#definesetinf(a) memset(a,126,sizeof(a))

#definetc1(x) printf("Case %d: ",x)
#definetc2(x) printf("Case #%d: ",x)
#definetc3(x) printf("Case %d:\n",x)
#definetc4(x) printf("Case #%d:\n",x)

#definepr1(x) cout<<x<<"\n"
#definepr2(x,y) cout<<x<<""<<y<<"\n"
#definepr3(x,y,z) cout<<x<<""<<y<<""<<z<<"\n"
#definepr4(w,x,y,z) cout<<w<<""<<x<<""<<y<<""<<z<<"\n"
#definefastios::sync_with_stdio(0)
#definereadfreopen("input.txt","r",stdin)
#definewritefreopen("output.txt","w",stdout)
#defineprflag1(flag) printf("%s\n",(flag)?"YES":"NO")
#defineprflag2(flag) printf("%s\n",(flag)?"Yes":"No")
#defineprflag3(flag) printf("%s\n",(flag)?"yes":"no")
/* defining macros */

usingnamespacestd;

template <classT> inline T bigmod(T b, T p, T m)
{
 T ret;
if(p==0) return1;
if(p&1)
 {
 ret=(bigmod(b,p/2,m)%m);
return ((b%m)*ret*ret)%m;
 }
else
 {
 ret=(bigmod(b,p/2,m)%m);
return (ret*ret)%m;
 }
}
/* template functions */

typedeflonglongLL;
typedefunsignedlonglongULL;
typedef pair<int, int>pii;
typedef pair<LL, LL>pll;
typedef vector<int>vi;
typedef vector<LL>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
/* type definition */

int dx4[]= {1,-1,0,0};
int dy4[]= {0,0,1,-1};
int dx6[]= {0,0,1,-1,0,0};
int dy6[]= {1,-1,0,0,0,0};
int dz6[]= {0,0,0,0,1,-1};
int dx8[]= {1,-1,0,0,-1,1,-1,1};
int dy8[]= {0,0,1,-1,1,1,-1,-1};
int dkx8[]= {-1,1,-1,1,-2,-2,2,2};
int dky8[]= {2,2,-2,-2,1,-1,1,-1};
/* direction array */

int tc=1;
constdouble eps=1e-9;
constdouble pi=acos(-1.0);
constlonglongint mx=1e5;
constlonglongint mod=1e9+7;
/* global declaration */

int a[mx+5],n;

intpartition(int l, int r)
{
int i,j;
 i=l-1;
for(j=l;j<r;j++)
 {
if(a[j]<=a[r]) swap(a[++i],a[j]);
 }
swap(a[++i],a[r]);
return i;
}

voidquick_sort(int l, int r)
{
if(l<r)
 {
int m=partition(l,r);
quick_sort(l,m-1);
quick_sort(m+1,r);
 }
return;
}

intmain()
{
int i;
while(cin>>n)
 {
for(i=1;i<=n;i++) scanf("%d",&a[i]);
quick_sort(1,n);
for(i=1;i<=n;i++) printf("%d ",a[i]);
 nl;
 }
return0;
}