/*#include <stdio.h>
int stack[100000]={},top=-1;
void push(int n)
{
stack[++top]=n;
}
void pop()
{
if(top!=-1)
stack[top--]=0;
}
int main()
{
int i,j,n,s=0,d[100000];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&d[i]);
for(i=n-1;i>=0;i--)
{
for(j=top;j>-1;j--)
{
if(stack[j]>=d[i])
break;
else
pop();
}
if(j<=-1)
s++;
push(d[i]);
}
printf("%d",s);
}
*/
/**
5 1 4 2 3 - > 1 2 3 4 5
정렬 : 바르게 줄세우는거
오름차순 내림차순
정렬의 종류
easy but slow -> 버블, 선택, 삽입 -> 걷기, 자전거, 버스
hard but fast -> 퀵, 기수, 병합, 힙 -> KTX, 비행기, 전투기
데이터가 조금, 속도가 느려도 별 상관없을때 ? ->
데이터가 좀 많고, 속도가 빨라야돼 ->
절대적으로 빠르거나 느린 정렬 기법은 없음!!! 상황에따라 다름!!!
1. 버블정렬
장점 : 코드가 엄청 간단
단점 : 항상 느리다
-> 어느정도 개선해서 사용하기
5 1 4 2 3
round1.
1 5 4 2 3
1 4 5 2 3
1 4 2 5 3
1 4 2 3 : 5
round2.
1 4 2 3 5
1 2 4 3 5
1 2 3 : 4 5
round3.
1 2 3 4 5
1 2 3 4 5
1 2 : 3 4 5
round4.
1 2 3 4 5
1 : 2 3 4 5
round5. 5개중에 4개가 자기자리에있으니까 나머지는 안찾아도돼
*/
/*#include <stdio.h>
int a[10001],n,i,j,temp;
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
for(j=1;j<n-i+1;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;
}*/