2750번 정렬(O(n^2)) BOJ 백준 C언어

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

구현

O(n^2)을 사용하는 방법이므로 삽입정렬 / 선택정렬 / 버블정렬 / 퀵정렬 등을 사용할 수 있다.

퀵정렬의 경우에는 피벗값에 따라 걸리는 시간이 바뀌기때문에 최선 O(nlogn)부터 최악O(n^2) 이다. 

1. 삽입정렬을 사용한 방법

#include <stdio.h>

int main() {
    int i = 0, j = 0, a, b, temp;
    int arr[1001] = { 0 };

    scanf("%d", &a);

    b = a;

    while (i < a) {
        scanf("%d", &arr[i]);
        i++;
    }

    while (j < b) {
        i = 0;
        while (i < b - 1) {
            if (arr[i] > arr[i + 1]) {
                temp = arr[i + 1];
                arr[i + 1] = arr[i];
                arr[i] = temp;
            }
            i++;
        }
        b--;
    }

    i = 0;
    while (i < a) {
        printf("%d\n", arr[i]);
        i++;
    }

    return 0;
}

 

2. 선택정렬을 사용한 방법

#include <stdio.h>

int main(int argc, char* argv[]) {
    int i, j, num, min, idx = 0, temp;
    int arr[1001] = { 0 };
    scanf_s("%d", &num);

    for (i = 0; i < num; i++) {
        scanf_s("%d", &arr[i]);
    }

    for (i = 0; i < num; i++) { //선택 정렬
        min = 9999;
        for (j = i; j < num; j++) {
            if (min > arr[j]) {
                min = arr[j];
                idx = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = temp;
    }
    for (i = 0; i < num; i++) {
        printf("%d\n", arr[i]);
    }
    return 0;
}

 

3. 버블정렬을 사용한 방법

#include <stdio.h>

int main() {
    int i = 0, j = 0, num, temp;
    int arr[1001] = { 0 };

    scanf_s("%d", &num);
    for (i = 0; i < num; i++){
        scanf_s("%d", &arr[i]);
    }
    for (i = 0; i < num; i++) {
        for (j = 0; j < num - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for (i = 0; i < num; i++) {
        printf("%d\n", arr[i]);

    }

    return 0;
}

 

4. 퀵정렬을 사용한 방법

#include <stdio.h>

void QuickSort(int* data, int start, int end) {
    if (start >= end) {
        return;
    }

    int key = start;
    int i = start + 1;
    int j = end;
    int temp;

    while (i <= j) {
        while (data[key] >= data[i] && i <= end) { //data[key] <= data[i] 이고
            i++;
        }
        while (data[key] <= data[j] && j > start) { //data[key] >= data[j] 이면 내림차순정렬
            j--;
        }
        if (i > j) {
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        }
        else {
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }
    QuickSort(data, start, j - 1);
    QuickSort(data, j + 1, end);
}

int main(void) {
    int i, num;
    int arr[1001] = { 0 };

    scanf_s("%d", &num);
    for (i = 0; i < num; i++) {
        scanf_s("%d", &arr[i]);
    }

    QuickSort(arr, 0, num - 1);

    for (i = 0; i < num; i++) {
        printf("%d\n", arr[i]);

    }
    return 0;
}

정리

기본적으로 선택정렬 삽입정렬 버블정렬은 대부분의 경우에서 어디서도 사용되지 않지만 기본적인 개념을 이해하고 있어야하기에 전체적으로 정리해 보았다.

또한 퀵정렬의 경우에도 최악의 시간이 걸릴 경우 O(n^2)이기에 많은 경우에서는 사용되지 않는다.

병합정렬 / 힙정렬 / 카운팅정렬에 대해서도 나중에 한번 다시 정리 후 글을 올려야겠다.