https://www.acmicpc.net/problem/2751
Idea
원래 정렬은Quick Sort
를 직접 구현해서 사용했지만 자꾸 시간 초과가 나왔다..
#include <stdio.h>
void quickSort(int arr[], int L, int R);
int main(void) {
int arr[1000001];
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
quickSort(arr, 0, N - 1);
for (int i = 0; i < N; i++) {
printf("%d\n", arr[i]);
}
return 0;
}
void quickSort(int arr[], int L, int R) {
int left = L, right = R;
int pivot = arr[(L + R) / 2];
int temp = 0;
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
if (L < right) {
quickSort(arr, L, right);
}
if (left < R) {
quickSort(arr, left, R);
}
}
내 코드에 문제가 있는지 언어의 한계인지 뭐가 문제인지 몰라 이것저것 다 해봤다.
다른 사람의 퀵 정렬 코드를 가져와서 써보기도 하고 언어를 바꿔서 Java 로 해보기도 했다.
결국 다 실패하고 구글링을 했는데 Quick Sort
의 한계였다. 최악의 상황엔 시간복잡도가 O(N^2)까지 발생한다고 한다.
그래서 c언어 헤더파일에 내장되어 있는 qsort
를 사용하기로 했다.
qsort
는 기본적으로 비교 함수를 내가 직접 만들어야 되는데 처음 써보는거라 다른 개발자들의 compare함수를 빌려 사용했다.
int compare (const void *a, const void *b) {
int num1 = *(int *)a;
int num2 = *(int *)b;
if (num1 < num2) {
return -1;
}
if (num1 > num2) {
return 1;
}
return 0;
}
qsort
의 작동원리는 제대로 이해하지 못했지만 리턴값을 보고 알아서 비교하는 듯 하다.
qsort(정렬할배열, 요소개수, 요소크기, 비교함수);
뭐 그렇대요..,
Code
#include <stdio.h>
#include <stdlib.h>
int compare (const void *a, const void *b);
int main(void) {
int arr[1000001] = { 0, };
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
qsort(arr, N, sizeof(int), compare);
for (int i = 0; i < N; i++) {
printf("%d\n", arr[i]);
}
return 0;
}
int compare (const void *a, const void *b) {
int num1 = *(int *)a;
int num2 = *(int *)b;
if (num1 < num2) {
return -1;
}
if (num1 > num2) {
return 1;
}
return 0;
}