/*버블정렬
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf_s("%d", &n);
for (i = 1; i <= n; i++)
scanf_s("%d", &a[i]);
for (i = 1; i < n; i++)
{
for (j=1;j<=n-i;j++)
// 이 부분에 들어가야 될 코드를 작성하여 제출
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (i = 1; i <= n; i++)
printf("%d\n", a[i]);
return 0;
}*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf_s("%d", &n);
for (i = 1; i <= n; i++)
scanf_s("%d", &a[i]);
for (i = 1; i < n; i++)
{
int comp = 0;
for (j = 1; j <= n - i; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
comp++;
}
}
if (comp == 0)
{
printf("%d\n", i-1);
return 0;
}
}
printf("%d\n", n-1);
return 0;
}*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf_s("%d", &n);
for (i = 1; i <= n; i++)
scanf_s("%d", &a[i]);
for (i = 1; i < n; i++)
{
int comp = 0;
for (j = 1; j <= n - i; j++)
{
if (a[j] < a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
comp++;
}
}
if (comp == 0)
{
for (i = 1; i <= n; i++)
printf("%d ", a[i]);
return 0;
}
}
for (i = 1; i <= n; i++)
printf("%d ", a[i]);
return 0;
}*/
/*구조체 내림차순
#include<stdio.h>
int n;
typedef struct _info
{
char name[100];
int score;
}INFO;
int main() {
INFO a[105] = { 0 };
INFO temp;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%s", &a[i].name, 100);
scanf_s("%d", &a[i].score);
}
for (int i = 1; i < n; i++)
{
int comp = 0;
for (int j = 1; j <= n - i; j++)
{
if (a[j].score < a[j + 1].score)
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
comp++;
}
}
if (comp == 0)
{
printf("%s", a[3].name);
return 0;
}
}
printf("%s", a[3].name);
return 0;
}*/
/*선택정렬
#include <stdio.h>
int a[10001];
int n, i, j, temp, min;
int main() {
scanf_s("%d", &n);
for (i = 1; i <= n; i++)
scanf_s("%d", &a[i]);
for (i = 1; i < n; i++)
{
min = i;
for (j = i + 1; j <= n; j++)
{
// 이 부분에 들어가야 될 코드를 작성하여 제출
if (a[min] > a[j])
{
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (i = 1; i <= n; i++)
printf("%d\n", a[i]);
return 0;
}*/
/*구조체 오름차순 선택정렬
#include<stdio.h>
int n, min;
typedef struct _gas
{
int a;
int b;
}GAS;
int main() {
GAS c[105] = { 0 };
GAS temp;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d %d", &c[i].a, &c[i].b);
}
for (int i = 1; i < n; i++)
{
min = i;
for (int j = i + 1; j <= n; j++)
{
if (c[min].a > c[j].a)
{
min = j;
}
}
temp = c[i];
c[i] = c[min];
c[min] = temp;
}
for (int i = 1; i <= n; i++) {
printf("%d %d\n", c[i].a, c[i].b);
}
return 0;
}*/
/*삽입정렬
#include <stdio.h>
int a[10001];
int n, i, j, temp, key;
int main() {
scanf_s("%d", &n);
for (i = 1; i <= n; i++)
scanf_s("%d", &a[i]);
for (i = 2; i <= n; i++)
{
key = a[i];
for (j =i-1;j>=1 &&key<a[j];j--)
{
a[j + 1] = a[j];
}
a[j + 1] = key;
}
for (i = 1; i <= n; i++)
printf("%d\n", a[i]);
return 0;
}*/
/*구조체 오름차순 버블정렬 strcmp
#include<stdio.h>
#include<string.h>
typedef struct _sche {
char a[105];
int b;
}SCHE;
int main() {
int n,y,m,d;
SCHE z[105] = { 0 };
SCHE temp;
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%s", &z[i].a,105);
scanf_s("%d", &y);
scanf_s("%d", &m);
scanf_s("%d", &d);
z[i].b = y * 10000 + m * 100 + d;
}
for (int i = 1; i < n; i++)
{
int comp = 0;
for (int j = 1; j <= n - i; j++)
{
if (z[j].b > z[j+1].b)
{
temp = z[j];
z[j] = z[j + 1];
z[j + 1] = temp;
comp++;
}
else if (z[j].b == z[j + 1].b)
{
if (strcmp(z[j].a, z[j + 1].a) > 0)
{
temp = z[j];
z[j] = z[j + 1];
z[j + 1] = temp;
}
}
}
if (comp == 0)
{
for (int i = 1; i <= n; i++) {
printf("%s\n", z[i].a);
}
return 0;
}
}
for (int i = 1; i <= n; i++) {
printf("%s\n", z[i].a);
}
return 0;
}*/
/*
퀵정렬
20 18 50 40 9 19 5 25
1.pivot 기준
ex)20
*/
#include<stdio.h>
int n,temp;
int a[100005] = { 0 };
void swap(int p, int q)
{
int t = a[p];
a[p] = a[q];
a[q] = t;
}
void quick_sort(int left, int right)
{
int low = left;
int high = right;
int pivot = left;
if (left >= right) return;
do {
while (a[low] < a[pivot])
{
low++;
}
while (a[high] > a[pivot])
{
high--;
}
if (low < high) {
swap(low, high);
}
} while (low < high);
swap(pivot, high);
quick_sort(left, high - 1);
quick_sort(high + 1, right);
}
int main() {
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &a[i]);
}
quick_sort(1, n);
for (int i = 1; i <= n; i++) {
printf("%d\n", a[i]);
}
return 0;
}