2750 : 수 정렬하기 (C)

2750번: 수 정렬하기

---

#include<stdio.h>

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

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

    int a[n];

    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for(int i = 0; i < n; i++) {
        min = 1001;
        for(int j = i; j < n; j++) {
            if(min > a[j]) {
                min = a[j];
                index = j;
            }
        }
        swap(&a[i], &a[index]);
    }

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

    return 0;
}

- 선택 정렬을 사용하여 구현한 알고리즘.

배열에서 가장 작은 값을 탐색 O(N), 그리고 앞으로 보내는데 O(N)의 시간복잡도를 가짐으로

O(N^2)의 시간 복잡도를 가진다.

 

#include<stdio.h>

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

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

    int a[n];

    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for(int i = 0; i < n - 1; i++) {
        int j = i;
        while(j >= 0 && a[j] > a[j + 1]) {
            swap(&a[j], &a[j + 1]);
            j--;
        }
    }

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

    return 0;
}

- 삽입 정렬을 이용하여 구현한 알고리즘.

배열의 첫 값과 다음 값을 계속 비교하여 앞으로 보낸다.

이것도 마찬가지로 O(N^2)의 시간 복잡도를 가진다.