/*
#include <stdio.h>
typedef struct{
int a,b;
}tds;
int main()
{
tds arr[101], temp;
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %d", &arr[i].a, &arr[i].b);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j < n + 1 - i; j++){
if(arr[j].a > arr[j + 1].a){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(int i = 1; i <= n; i++){
printf("%d %d\n", arr[i].a, arr[i].b);
}
}
*/
/*
#include <stdio.h>
typedef struct{
int a, b, c;
char name[11];
}std;
int main()
{
int n, x=1, y=1;
std arr[101], temp;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%s%d%d%d",arr[i].name,&arr[i].a,&arr[i].b,&arr[i].c);
}
for(int i = 0; i < n-1; i++){
for(int j = 0; j < n - 1 - i; j++){
if(arr[j].a < arr[j+1].a){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j+1] = temp;
}
}
}
for(int i = 0; i < n; i++){
if(arr[0].b<arr[i].b) x++;
if(arr[0].c<arr[i].c) y++;
}
printf("%s %d %d", arr[0].name, x, y);
}
4531 그냥정렬
1420 3017 3019 구조체정렬
3014 ( 기존정렬x, 메모이제이션이용한 정렬)
1452 (퀵정렬)
#include <stdio.h>
int arr[100001] = {};
void swap(int a, int b)
{
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void qs(int s, int e)
{
if(s>=e) return ;
int pivot = s;
int left=s, right=e+1;
do{
do{
left++;
}while(arr[left]<arr[pivot]);
do{
right--;
}while(arr[right]>arr[pivot]);
if(left<right){
swap(left,right);
}
}while(left<right);
swap(pivot,right);
qs(s,right-1);
qs(right+1,e);
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
qs(0, n-1);
for(int i = 0; i < n; i++){
printf("%d\n", arr[i]);
}
}
#include <stdio.h>
int main()
{
int n, arr[100001] = {}, temp;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &temp);
arr[temp]++;
}
for(int i = 0; i < 100001; i++){
for(int j = 0; j < arr[i]; j++){
printf("%d ", i);
}
}
}
#include <stdio.h>
typedef struct{
char name[11];
int p;
}std;
int main()
{
std arr[51], temp;
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%s%d", arr[i].name, &arr[i].p);
}
for(int i = 0; i < n + 1; i++){
for(int j = 0; j < n - 1 - i; j++){
if(arr[j].p < arr[j+1].p){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printf("%s", arr[2].name);
}
*/