/*
#include <stdio.h>
#include <string.h>
typedef struct
{
char bucket [100];
int bj;
}a;
int main()
{
a bucket_list[101],temp;
int n,i,j, x, y, z;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s %d %d %d",bucket_list[i].bucket,&x,&y,&z);
bucket_list[i].bj=x*10000+y*100+z;
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(bucket_list[j].bj>bucket_list[j+1].bj)
{
temp=bucket_list[j];
bucket_list[j]=bucket_list[j+1];
bucket_list[j+1]=temp;
}
else if(bucket_list[j].bj==bucket_list[j+1].bj)
{
if(strcmp(bucket_list[j].bucket,bucket_list[j+1].bucket)>0)
{
temp=bucket_list[j];
bucket_list[j]=bucket_list[j+1];
bucket_list[j+1]=temp;
}
}
}
}
for(i=1;i<=n;i++)
printf("%s\n",bucket_list[i].bucket);
// char a[50]="love";
// char b[50]="abcd";
// strcmp(a,b)>0
// strcmp(b,a)<0
// strcmp(a,"love")==0
}
버블
코드 쉬워
항상 느려> 개선
선택
삽입
코드 조금 어려워
"데이터가 정렬이어느정도되어있는경우" 굉장히빨라
코드 짱어려워
퀵정렬(재귀), 병합정렬, 힙정렬, 기수정렬, .......
#include <stdio.h>
int a[10001];
int n, i, j, temp, key;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%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;
}
hint . 메모이제이션
key 라는 변수에 i에 있는 값을 저장 해놓은 후 key값보다 작은수를 count에 저장한후 위치만큼 배열에 냅둔다
#include <stdio.h>
int main()
{
int memo[100001]={};
int n,i,j,key;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&key);
memo[key]++;
}
//memo[i] = i가 입력된 횟수
// 1을 memo[1]번 출력
// 2를 memo[2]번 출력
//.....
//100000을 memo[100000]번 출력
for(i=0;i<=100000;i++)
{
if(memo[i]!=0)
{
for(j=1;j<=memo[i];j++)
{
printf("%d ",i);
}
}
}
return 0;
}
f(n) : n번 째 피보나치수
s가 피벗값보다크고 e위치가 피벗 값보다 작으면 교환후 한칸진전
만약 하나는 아닌데 하나는 맞다면 맞는것은 진전 아닌것은 기다린다
결국은 끝까지 안나오거나 첫번째 결과가나온다
그걸 다한후 s위치와 피벗 위치를 교환한다
그리고 피벗은 가운데에 있으므로 그 나머지에 있는 부분을 위와같은 알고리즘으로 반복
그러면 정렬완성
그리고 참고로 완전히 시간을 단축하려면 do while 사용
*/
//#include <stdio.h>
//int f(int n)
//{
// if(n<=2) return 1;
// return f(n-1)+f(n-2);
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// printf("%d",f(n));
//
//}
#include <stdio.h>
int arr[100001]= {};
void swap(int x, int y)
{
int t=arr[x];
arr[x]=arr[y];
arr[y]=t;
}
//void quick_sort
void qs(int s, int e) //arr[s] ~arr[e] 퀵정렬하세요
{
if(s>=e)
return ;
int pivot=s; //기준값의 위치는 맨 첫번째값
int low=s, high=e+1;
//arr[pivot]값을 기준으로 작은건 왼쪽, 큰건 오른쪽에 정렬
do
{
do
{
low++;
}while(arr[pivot] > arr[low]);
do{
high--;
}while(arr[pivot] < arr[high]);
if(low<high)
{
swap(low,high);
}
} while(low<high);
swap(pivot,high);
qs(s,high-1);
qs(high+1,e);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%d",&arr[i]);
qs(1,n);
for(i=1; i<=n; i++)
printf("%d\n",arr[i]);
return 0;
}