[백준/C언어] 2750번 - 수 정렬하기

백준 웹사이트 "2750번 - 수 정렬하기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

2750번: 수 정렬하기

---

소스 코드

#include <stdio.h>

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

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

    // Bubble Sort
    while(1){
        int swapped = 0;
        for(int i=0; i<N-1; i++){
            //i와 i+1 비교, i가 더 크다면 swap
            if(arr[i]>arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swapped = 1;
            }
        }
        if(!swapped) //변한 것이 없다면 break
            break;
        N = N-1; //없어도 무관하지만, 있으면 더 효율적
    }

    // 결과 출력
    for(int i=0; i<len; i++){
        printf("%d\n", arr[i]);
    }
}

---

문제 풀이

  시간 복잡도가 \(O(n^2)\)인 정렬 알고리즘을 짜는 문제입니다. \(O(n^2)\)의 시간 복잡도는 정렬 알고리즘 중에서 효율이 가장 낮은 축에 속하며, Insertion Sort (삽입 정렬)나 Bubble Sort (거품 정렬) 등이 포함됩니다. 이러한 정렬의 최대 장점은 이해가 쉽고, 짜기가 쉽다는 것입니다. 따라서 정렬 알고리즘을 처음 접하는 사람들이 공부하고, 직접 짜보기 좋습니다.

  이 문제에서 사용할 정렬 알고리즘은 Bubble Sort (거품 정렬)입니다. 수들이 정렬되는 모습이 마치 물 속에서 거품이 위로 뜨는 것과 같다고 하여 붙여진 이름입니다.

Bubble Sort (출처: 위키피디아 "Bubble Sort")

Bubble Sort의 원리는 다음과 같습니다. 앞에서부터 두 개의 숫자씩 비교를 하여 정렬되어 있지 않다면 (즉, 앞의 숫자보다 뒤의 숫자가 작다면) 둘의 위치를 바꿔줍니다. 이렇게 한 차례 지나가게 되면, 정렬의 숫자들 중 가장 큰 숫자는 정렬의 맨 끝에 위치하게 됩니다. 이러한 과정을 여러 번 반복하다보면 정렬의 모든 숫자는 정렬됩니다. 앞에서부터 두 숫자씩 비교하여 전체 숫자들을 한 차례 검사했을 때, 위치를 바꾸는 경우가 없다면 모든 숫자들이 정렬되어 있다는 뜻이 되므로 정렬을 종료합니다.

  소스 코드의 Line 14 ~ 28이 Bubble Sort에 해당됩니다. Line 15의 'swapped' 변수는 전체 숫자들을 한 차례 검사했을 때, 위치를 바꾸는 경우가 있는지에 대한 여부입니다. Line 16 ~ 24에서 한 차례 검사하는 동안, 바꾸는 경우가 있다면 swapped는 1로 바뀌고, 없다면 처음 초기화한 0으로 남아 Line 26의 break를 통해 while문을 빠져나갑니다. 빠져나가기 전까지 while문을 반복하며, 숫자들을 하나씩 정렬합니다.

  추가로, Line 27의 'N = N-1'은 없어도 무관하지만, 있으면 더 효율적으로 정렬을 진행할 수 있습니다. 검사를 한 차례 진행하면, 가장 큰 숫자는 정렬의 맨 끝에 위치하게 됩니다. 따라서 다음 차례를 진행할 때는, 마지막 숫자는 제외하고 생각하도 되겠죠? 마찬가지로 세 번째 차례에서는 마지막 두 숫자를 제외할 수 있습니다. 그런 의미에서, 한 차례 검사할 때마다 N의 값을 1만큼씩 줄입니다.