문제 링크: https://www.acmicpc.net/problem/2750

입력

Line 1: 정수 \(N(1≤N≤1000)\)이 주어진다.

Line 2~(N+1): 절대값이 \(1000\)보다 작거나 같은 정수가 한 줄에 하나씩 주어진다. (중복 없음)

출력

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

C99로 구현하였다.

1. 정렬: 비교와 교환 작업

정렬은 일반적으로 기본적으로 크기 비교를 하여 순서대로인지 파악하고, 아닐 경우 원소를 이동시켜 순서를 변경하는 작업이다. 우선 인접 원소를 비교하여 순서에 맞지 않으면 원소를 교환해주는 작업을 구현하자.

우선 int배열 array와 배열의 크기 size가 인수로 주어지는 함수 sort에 대해서,

void sort(int* array,int size){
    int i,tmp;
    for(i=0;i<size-1;++i){
    	if(array[i]>array[i+1]){
    	    tmp=array[i];
    	    array[i]=array[i+1];
            array[i+1]=tmp;
    	}
    }
}

와 같이 구현하였다.

index i는 \([0,size-2]\)를 순회하며 array[i]가 array[i+1]보다 큰 경우만 두 원소를 교환하고 있다. 이는 현재 i가 탐색한 범위 내에서 가장 큰 원소들을 계속해서 그 다음으로 보내는 작업이다. 이 순회를 마치면 \([0,size-1]\) 범위의 array 원소들중 가장 큰 원소가 array+size-1에 위치하게 된다.

아직 부족하다. 위 순회가 한번 실행되면 가장 마지막 값이 가장 큰 값이라는 것만 보장될 뿐이다. 하지만 위 순회를 반복해 그 다음 큰 값을 계속해서 찾아내 차례로 저장하도록 반복문을 만들수 있다.

void sort(int* array,int size){
  int i,j,tmp;
  for(i=size-1;i>=0;--i){
    for(j=0;j<i;++j){
      if(array[j]>array[j+1]){
        tmp=array[j];
        array[j]=array[j+1];
        array[j+1]=tmp;
      }
    }
  }
}

앞서 살펴본 순회는 위 코드에서 반복문 안에 중첩되어 순회가 반복되도록 구현되어 있다. (i가 j로, size-1은 i로 바꾸었다.) j를 \([0,i-1]\)범위에서 순회시켜 \([0,i]\)범위에서 가장 큰 원소를 array+i에 위치시키고 i는 다시 감소하여 순회를 반복한다. 결국 array[size-1]부터 array[1]까지 역순으로 그 수를 찾으며 array의 \([0,size-1]\)범위가 오름차순으로 정렬된다.

2. Bubble Sort : 거품 정렬

void bubbleSort(int* array,int size){
  int i,j,tmp;
  for(i=size-1;i>=0;--i){
    for(j=0;j<i;++j){
      if(array[j]>array[j+1]){
        tmp=array[j];
        array[j]=array[j+1];
        array[j+1]=tmp;
      }
    }
  }
}

앞선 단계에서 다룬 정렬 알고리즘을 Bubble Sort(거품정렬)이라 하는데, 거품 정렬로 원소들을 정렬할 때 이를 위와 같이 시각화하면, 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보여 이러한 이름이 붙었다.

보다시피 인수 size만큼 반복될 수 있는 반복문이 이중으로 구성되어 있어 평균적으로 \(O(n^2)\) 의 시간복잡도를 가지기 때문에 자료의 크기가 커질수록 처리시간이 기하급수적으로 늘어나게 된다.

나무위키: 정렬 알고리즘 - 버블 정렬

거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 이미 정렬된 자료를 정렬하는 바보짓을 왜 하냐는 의문이 들 수 있지만, 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다. 가장 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식이다. 다른 몇 가지 정렬 방식과 비교해도 효율이 대략 시망. 이해하기 쉽고 코드가 짧은 덕에 각종 교습서에서 정렬 알고리즘의 예시로 많이 보여주며, 입력량이 작으면 어지간한 비효율적인 방법도 씹어먹고 수행이 가능하지만 실제 개발에서는 전혀 쓰이지 않는다고 봐도 무방하다. 정말 어지간한 경우가 아닌 이상 버블 소트는 피해야 한다.

구현 해본 것에 의의를 두자

3. 입출력 및 데이터 저장

int main(void){
  int N,i,*array;
  
  scanf("%d\n",&N);
  array=malloc(N*sizeof(int));
  for(i=0;i<N;++i)
    scanf("%d",array+i);
  
  bubbleSort(array,N);
  for(i=0;i<N;++i)
    printf("%d\n",array[i]);
  
  free(array);
  return 0;
}

간단하다.

4. 최종 코드

#include <stdio.h>
#include <malloc.h>

void bubbleSort(int* array,int size){
  int i,j,tmp;
  for(i=size-1;i>=0;--i){
    for(j=0;j<i;++j){
      if(array[j]>array[j+1]){
        tmp=array[j];
        array[j]=array[j+1];
        array[j+1]=tmp;
      }
    }
  }
}

int main(void){
  int N,i,*array;
  
  scanf("%d\n",&N);
  array=malloc(N*sizeof(int));
  for(i=0;i<N;++i)
    scanf("%d",array+i);
  
  bubbleSort(array,N);
  for(i=0;i<N;++i)
    printf("%d\n",array[i]);
  
  free(array);
  return 0;
}

테스트 범위가 매우 작아서 가능한 일이었다.

제출 소스