qsort의 정확한 구현 방법에 대해서는 표준에서 정의하고 있지 않지만 (표준에는 qsort의 최악의 수행 시간이 n lg n 이어야 한다는 말도 없습니다), 적어도 백준 채점 서버에서 qsort는 상당히 빠른 속도로 잘 돌아갑니다. 한 가지 아쉬운 점이 있다면, 비교 연산을 전부 커스텀 함수를 호출해서 하기 때문에 C++의 std::sort보다는 어쩔 수 없이 느리다는 것이지만, 그럼에도 불구하고 평균 / 최악의 시간 모두 제법 훌륭한 편이라고 느끼고 있습니다.
zxkyh100 6년 전 1
비쥬얼 스튜디오에서는 잘 돌아가는데 서버에서는 런타임 오류가 납니다ㅜㅜ
어디서 오류가나는지 알 수 가 없어서 이렇게 질문 올려요
#include <stdio.h>
void quick_sort(int *arr, int start, int end);
void swap(int *a, int *b);
int main() {
int n;
scanf("%d", &n);
int *arr;
arr = (int *)malloc(sizeof(int)*n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
quick_sort(arr, 0, n - 1);
printf("%.0f\n", (double)sum / n); // 평균을 구함
printf("%d\n", arr[n / 2]); // 중간값을 구함
int *val_arr;
val_arr = (int*)calloc(n,sizeof(int));
//calloc 을 사용하면서 동적할당을 하면서 초기화를 진행
int val_n = 1;
val_arr[0] = arr[0]; // val = 최대빈도수의 값 배열
int max = 1, fre_n = 1; // max = 최대 빈도수, n = 현재 빈도수
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
{
fre_n++;
}
else {
if (fre_n > max) {
max = fre_n;
for (int j = 0; j < val_n; j++) {
val_arr[j] = 0;
}
val_arr[0] = arr[i-1];
val_n = 1;
fre_n = 1;
}
else if (fre_n == max) {
val_arr[val_n] = arr[i];
val_n++;
}
else {
fre_n = 1;
}
}
}
if (val_arr[1] != 0) {
printf("%d\n", val_arr[1]);
}
else {
printf("%d\n", val_arr[0]);
}
printf("%d", arr[n - 1] - arr[0]);
}
void quick_sort(int *arr, int start, int end) {
if (start > end) return;
int mid = (start + end) / 2;
int pivot = arr[mid];
swap(&arr[start], &arr[mid]);
int p = start + 1;
int q = end;
while (1)
{
while (arr[p]<=pivot)
{
p++;
}
while (arr[q]>pivot)
{
q--;
}
if (p > q) break;
swap(&arr[p], &arr[q]);
}
swap(&arr[start], &arr[q]);
quick_sort(arr, start, q - 1);
quick_sort(arr, q + 1, end);
}
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}