[백준] 11931 수 정렬하기 4

🆀 문제

주어진 수에 대하여 내림차순 정렬하기

---

🅰 나의 풀이

흔한 내림차순 정렬하기 문제이지만 시간 제한이 걸려있다는 게 핵심이다.

pivot이 잘 정해진다면 평균적으로 O(n log n)의 시간 복잡도를 가지는 Quick sort를 선택했다.

void quicksort(int arr[], int l, int r){
    if (l >= r) return; 

    int left = l;
    int right = r;
    int pivot =  arr[(l+r) / 2];

    while (l < r){ 
    // 오름차순 정렬을 하고 싶다면 부등호 방향을 바꾸면 된다
        while (arr[l] > pivot) l++; // pivot보다 클 때까지 l을 증가
        while (arr[r] < pivot) r--; // pivot보다 작을 때까지 r을 감소
        
        if (l <= r) { // ??
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            l++;
            r--;
        }
    }
    quicksort(arr, left, r);
    quicksort(arr, l, right);
}

int main() {
    int n;
    scanf("%d", &n);

    int *arr = (int*)malloc(sizeof(int) * n);
    if (arr == NULL){
        printf("malloc err\n"); exit(1);
    }
    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 ", arr[i]);
    }

    free(arr);

    return 0;
}

---

🆂 다른 풀이

1.

swap 전에 `if (l <= r)`처럼 조건문이 한번 더 필요했던 이유는

while의 `(l < r)` 조건이 있지만 내부에서 l과 r이 변하기 때문이다.

그런데 중복 조건처럼 보이고 마음에 안 든다.

    while (1){ 
        while (arr[l] > pivot) l++;
        while (arr[r] < pivot) r--;

        if (l > r) break;

        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        l++;
        r--;
    }

`break;`를 사용하면 중복 조건의 느낌을 지울 수 있고 더 직관적인 것 같다.

 

2.

C에는 qsort 함수가 있다...!!!

int compare(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

qsort(arr, n, sizeof(int), compare);

이렇게 compare 함수만 만들어주면 된다...!

---