PS시 어떤 정렬을 선택하는 것이 좋을까?

어떤 정렬을 선택해야할까?

원소(숫자, 문자열)가 있을 때 정렬하는 기법은 여려가지 알려져 있습니다.

ex) 단순히 두 원소를 비교해서 자리를 찾아가는 기본적인 Bubble Sort 시작해서 Quick Sort, Merge Sort

※ 정렬 알고리즘 비교

정렬 알고리즘 비교

PS 하다보면 문제에서 여러 원소 중 가장 큰 값, 상위 1~10등, 오름/내림차순 순서를 요구할 때가 있습니다.

시간 제한 까다롭지 않다면 어떤 기법을 사용하던 상관없을 것입니다.

 

가장 큰 원소를 찾는 경우

A) 굳이 정렬을 할 필요도 없습니다. for문으로 탐색하며 찾으면 되기 때문입니다. → O(N)

#include <stdio.h>
#include <stdlib.h>

inline int max(int A, int B) { return A > B ? A : B; }
enum {
    RANDOM = 1,
    FORWARD = 2,
    REVERSE = 3,
};

const int SIZE = 100;
int arr[SIZE];
void makeData(int mode) {
    if (mode == RANDOM) {
        for (int i = 0; i < SIZE; ++i) arr[i] = rand() % SIZE;
    }
    else if (mode == FORWARD) {
        for (int i = 0; i < SIZE; ++i) arr[i] = i;
    }
    else { /* mode == REVERSE */
        for (int i = 0; i < SIZE; ++i) arr[i] = SIZE - i - 1;
    }
}

int main() {
    makeData(RANDOM);
    int ans = 0;
    for (int i = 0; i < SIZE; ++i) {
        ans = max(ans, arr[i]);
    }
    printf("최대값: %d\n", ans);
}

※ Random Value는 난수 생성 (rand, srand, time)

[C / C++] 난수 생성 (rand, srand, time)

 

전체 원소를 크고/작은 순으로 배치하는 경우

A) 원소 배치 상태나 개수에 따라 성능이 좌우되지만 Random Value인 경우

    Merge Sort 혹은 Quick Sort  → O(N × log2N)

#include <stdio.h>
#include <stdlib.h>
enum {
    RANDOM = 1,
    FORWARD = 2,
    REVERSE = 3,
};
const int SIZE = 2e4;
int arr[SIZE], temp[SIZE];
void makeData(int mode) {
    if (mode == RANDOM) {
        for (int i = 0; i < SIZE; ++i) arr[i] = rand() % SIZE;
    }
    else if (mode == FORWARD) {
        for (int i = 0; i < SIZE; ++i) arr[i] = i;
    }
    else { /* mode == REVERSE */
        for (int i = 0; i < SIZE; ++i) arr[i] = SIZE - i - 1;
    }
}

void mergeSort(int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= end) temp[k++] = arr[j++];
    for (i = start; i <= end; ++i) {
        arr[i] = temp[i];
    }
}

void printTop10() {
    for (int i = 0; i < 10; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

int main() {
    makeData(RANDOM);
    printTop10();
    mergeSort(0, SIZE - 1);
    printTop10();
}

※ 출력 자체는 상위 10개만 출력하였습니다.

214  < 20,000 < 215 이므로 log220000 = 14.28 → N × log2N = 20000 × 14 = 280,000이며

PS에서 1억( 108)개를 처리하는데 1초 걸리므로 0.028 소요됩니다.

만약 이러한 작업이 1000번 호출된다면 28초가 소요된다고 보시면 됩니다.

 

위와 같은 조건에서 숫자가 큰 원소 10개를 선택

A) 삽입 정렬

     문제에서 상위 top10 결과만을 원하는 경우 상위 11번째 이후 Data가 어떤 것인지는 중요하지 않습니다.

     따라서, 1 ~ N개의 원소가 상위 10개 안에 들어가는지만 확인하면 됩니다. → O (N × 10)

#include <stdio.h>
#include <stdlib.h>
enum {
    EMPTY = -1,
    RANDOM = 1,
    FORWARD = 2,
    REVERSE = 3,
};

const int SIZE = 2e4;
int top[11], arr[SIZE];

void makeData(int mode) {
    if (mode == RANDOM) {
        for (int i = 0; i < SIZE; ++i) arr[i] = rand() % SIZE;
    }
    else if (mode == FORWARD) {
        for (int i = 0; i < SIZE; ++i) arr[i] = i;
    }
    else { /* mode == REVERSE */
        for (int i = 0; i < SIZE; ++i) arr[i] = SIZE - i - 1;
    }
}

void insertionSort() {
    // 상위 11개의 자리를 공석으로 만듭니다.
    for (int i = 0; i < 11; ++i) {
        top[i] = -1;
    }
    for (int i = 0; i < SIZE; ++i) {
        int pos;
        for (pos = 9; pos >= 0; pos--) {
            // 비교 대상이 없는 경우
            if (top[pos] == EMPTY) continue;
            
            // 비교 대상이 존재하는 경우
            if (top[pos] < arr[i]) {
                top[pos + 1] = top[pos];
            }
            else { // 더 이상 순위를 올리지 못하는 경우
                break;
            }
        }
        // 더 이상 올라가지 못한 위치 + 1 = 등수
        top[pos + 1] = arr[i];
    }
}
void printTop10(int data[]) {
    for (int i = 0; i < 10; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n\n");
}
int main() {
    makeData(RANDOM);
    printTop10(arr);
    insertionSort();
    printTop10(top);
}

 

삽입 정렬 구현 시 고려사항

- 10위가 밀려나서 11위 자리로 교환처리를 용이하기 위해서 11번째 자리 이용 (top[10])

- 10위(top[9])부터 ~ 1위(top[0])까지 상대보다 우세한 경우 상대는 아래 등수로 밀립니다.

  하지만 더 이상 등수를 올릴 수 없는 경우 break 합니다.

  ex) 1등인 경우 pos = -1이며, 4등인 경우 pos = 3으로 배열에는 top[pos + 1]에 위치합니다.

 

* Data의 상태에 따라서 모든 데이터가 10번씩 비교하지 않고 중간에 끝날 수도 있으며

   문제 요구 사항에 따라 적절한 정렬 기법을 이용해야 합니다.