https://www.acmicpc.net/problem/2750
퀵정렬로 풀었다. 최악의 시간복잡도가 O(n^2)인데 통과한걸 보니 테스트케이스가 좀 양심이 있었나보다.
#include <stdio.h>
#include <stdlib.h>
void quick_sort (int * arr, int start, int end) {
int pivot = arr[(start + end) / 2]; /* 오름차순 */
int i = start, j = end;
int temp;
do {
while (arr[i] < pivot) i++;
while (pivot < arr[j]) j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j) quick_sort(arr, start, j);
if (i < end) quick_sort(arr, i, end);
}
int main () {
int *arr = NULL;
int len, i;
scanf("%d", &len);
arr = (int *)malloc(len * sizeof(int));
for (i = 0; i < len; i++) {
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, len - 1);
for (i = 0; i < len; i++) {
printf("%d \n", arr[i]);
}
free(arr);
return 0;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 2609번 C언어 풀이 (0) | 2021.10.27 |
---|---|
백준 2751번 C언어 풀이 (0) | 2021.10.26 |
백준 1356번 C언어 풀이 (0) | 2021.10.25 |
백준 9037번 C언어 풀이 (0) | 2021.10.07 |
백준 5086번 C언어 풀이 (0) | 2021.10.07 |