반응형
https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
해당 문제는 수의 개수가 100만까지 있다. N^2로 하면 시간초과가 날게 뻔하다. 정렬 알고리즘 중에서 최대 NlogN까지의 시간복잡도를 갖는 애로 가야한다.
1) 퀵소트로 풀어봤다.
#include <stdio.h>
void quick (int arr[], int start, int end)
{
if (start>=end)
{
return;
}
int key = start;
int i = start+1;
int j = end;
int change;
while (i<=j)
{
while (arr[key]<=arr[i])
{
i++;
}
while (arr[j]>arr[key] && j>key)
{
j--;
}
if (i>j)
{
change = arr[j];
arr[j] = arr[key];
arr[key] = change;
}
else
{
change = arr[j];
arr[j] = arr[i];
arr[i] = change;
}
}
quick (arr,start,j-1);
quick (arr,j+1,end);
}
int main()
{
int i,number = 0;
scanf("%d",&number);
int arr[number];
for (i=0; i<number; i++)
{
scanf("%d",&arr[i]);
}
quick (arr, 0 , number-1);
for (i=0; i<number; i++)
{
printf("%d\n",arr[i]);
}
return 0;
}근데 퀵소트로 푸니까 시간초과가 나왔다. 아마 퀵소트의 경우는 Best, Avg케이스는 NlogN이지만 Worst케이스는 N^2가 나올 수 있기 때문인 것 같다.
따라서, NlogN 정렬 중 합병정렬이나 힙 정렬로 접근해보고자 한다.
-> 합병정렬
#include <stdio.h>
int sorted[1000000];
void merge (int arr[], int start, int mid, int end)
{
int i = start;
int j = mid+1;
int k = start;
while(i<=mid && j<=end)
{
if (arr[i]<=arr[j])
{
sorted[k] = arr[i];
i++;
}
else
{
sorted[k] = arr[j];
j++;
}
k++;
}
if (i>mid)
{
int t;
for (t=j; t<=end; t++)
{
sorted[k] = arr[t];
k++;
}
}
else
{
int t;
for (t=start; t<=mid; t++)
{
sorted[k] = arr[t];
k++;
}
}
int t;
for (t=start; t<=end; t++)
{
arr[t] = sorted[t];
}
}
void merge_sort (int arr[], int start, int end)
{
if (start<end)
{
int mid = (start+end)/2;
merge_sort (arr,start,mid);
merge_sort (arr,mid+1,end);
merge (arr,start,mid,end);
}
}
int main()
{
int i,number = 0;
scanf("%d",&number);
int arr[number];
for (i=0; i<number; i++)
{
scanf("%d",&arr[i]);
}
merge_sort (arr,0,number-1);
for (i=0; i<number; i++)
{
printf("%d\n",arr[i]);
}
return 0;
}반응형
'프로그래밍 > Algorithm' 카테고리의 다른 글
| [알고리즘] # 1. 그리디 알고리즘 (Greedy Algorithm) 이론과 예제 풀이 (0) | 2022.07.11 |
|---|---|
| [알고리즘] # 0. Big-O / 시간 복잡도(Time Complexity)와 거품 정렬 (Bubble Sort) (0) | 2022.02.18 |
