자료의 정렬과 탐색 - 1. 자료의 정렬 (1)

정렬의 개념

정렬(sort)이란, 특정 집합(목록, list)의 원소들을 일정한 순서에 따라 배치하는 것을 말합니다. 정렬의 대상이 되는 원소가 가진 속성 중 정렬의 기준이 되는 값을 Key(키) 값이라고 하며, 일반적으로 원소를 키값이 커지는 순으로 배치하는 것이 정렬입니다. 정렬중에는 새로운 원소가 추가되거나 기존의 원소가 삭제되면 안되며, 이를 무결성 이라고 합니다.

정렬의 사전적 정의는 비교적 간단하지만, 정렬을 효율적으로 수행하기 위한 과정은 다양하고 복잡합니다. 지금까지 다양한 정렬 알고리즘이 연구 및 개발되었으며 버블 정렬, 퀵 정렬, 삽입 정렬, 선택 정렬등의 알고리즘이 대표적입니다.

버블 정렬(Bubble sort)

버블 정렬은 간단히 말해서 두 인접한 원소를 비교하여 교환하는 과정을 반복하는 정렬 알고리즘 입니다. 배열(리스트)의 맨 앞에 있는 원소부터 시작해서 해당 원소와 그 다음 원소를 비교하고, 큰 값을 뒤로 보내는 과정을 반복하게 됩니다. 이것을 마지막 원소까지 반복하게 되면 가장 큰 원소가 맨 뒤에 위치하게 되며 이후 정렬되지 않은 원소들에도 같은 방법으로 반복하면 모든 원소에 대해 정렬이 완료됩니다.

단계	s[1]	s[2]	s[3]	s[4]	s[5]
초기	9	5	6	2	3
1단계	5	6	2	3	9
2단계	5	2	3	6	9
3단계	2	3	5	6	9
4단계	2	3	5	6	9
완료	2	3	5	6	9

위 표는 리스트의 처음 상태가 {9, 5, 6, 2, 3} 일때의 상황에서 버블정렬 하는 과정을 단계적으로 나타낸 표입니다. 버블 정렬이라는 이름은 정렬 수행 과정에서 키값이 큰 원소가 뒤로 가는 모습이 거품이 커지는 모습과 유사하다고 하여 붙여진 이름입니다. 버블 정렬은 정렬 알고리즘 중에서 최초로 연구 및 개발된 알고리즘으로, 다른 알고리즘들에 비해 쉽게 이해할 수 있고 구현이 간단하지만 비교와 교환하는 횟수가 많아 수행 속도가 느립니다.

#include <stdio.h>

int main(void) {
  int s[10];
  int n=-1;

  do{
    n++;
    scanf("%d", &s[n]);
  }while(n < 9);
  for (int i = 1; i <= 9; i++){
    for(int j = 0; j <= 9 - i; j++){
      if(s[j] > s[j+1]){
        int temp = s[j];
        s[j] = s[j+1];
        s[j+1] = temp;
      }
    }
  }

  for(int m = 0; m<10; m++){
    printf("%d ", s[m]);
  }
}

입력: 1 3 5 7 9 2 4 6 8 10
출력: 1 2 3 4 5 6 7 8 9 10

선택 정렬(Selection sort)

선택 정렬은 간단히 말해서 리스트의 원소중 최솟값을 선택하여 맨 앞에 위치한 원소와 교체하는 과정을 반복하는 정렬 알고리즘 입니다.

첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 맨 앞에 위치시키고, 다시 두 번째 자료를 세 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 두 번째 자리에 위치하는 이러한 과정들을 반복하여 정렬을 수행하게 됩니다.

단계	s[1]	s[2]	s[3]	s[4]	s[5]
초기	9	5	6	2(최솟값, 선택됨)	3
1단계	2	5	6	9	3(최솟값, 선택됨)
2단계	2	3	6	9	5(최솟값, 선택됨)
3단계	2	3	5	9	6(최솟값, 선택됨)
4단계	2	3	5	6	9(최솟값, 선택됨)
완료	2	3	5	6	9

위 표는 리스트의 처음 상태가 {9, 5, 6, 2, 3} 일때의 상황에서 선택정렬 하는 과정을 단계적으로 나타낸 표입니다. 선택 정렬이라는 이름은 정렬 수행 과정에서 가장 작은 수를 선택하는 연산이 수행되기 때문에 붙은 이름입니다. 선택 정렬은 일상생활 속에서 쉽게 찾을 수 있는 형태의 정렬인데, 바닥에 흩어진 카드를 순서대로 정리할때 눈에 보이는 수 중에 가장 작은 수부터 집어들어서 정리하는게 일반적인 방법이기 때문입니다.

선택 정렬은 버블 정렬과 같이 설계 및 구현이 간단하지만, 효율적인 정렬 알고리즘은 아닙니다. 원소의 개수가 적은 경우 적합한 알고리즘이며 버블 정렬은 큰 수부터 시작해 뒤쪽 부터 정렬되었지만, 선택 정렬은 작은 수 부터 시작해 앞쪽부터 정렬되는 특징이 있습니다.

//선택정렬 코드
#include <stdio.h>
int main()
{
	int i,m,j,temp;
	int s[10];
	for(m = 0; m <= 9; m++){   
	    scanf("%d", &s[m]);     //배열 s[]에 10개의 값을 입력받는 과정입니다. 
	}
    for(i = 0; i <= 8; i++){        //배열의 첫번째 자리부터 마지막-1번째 자리까지의 원소를
        for(j = i + 1; j <= 9; j++) //그 다음 위치의 원소부터 마지막 원소까지 반복하며
        {
            if(s[i] > s[j])         //최솟값을 찾는 비교를 수행합니다.
            {
                temp=s[i];
                s[i] = s[j];
                s[j] = temp;  //원소의 자리를 바꾸는 코드로, 한 원소의 값을 임시로 저장해놓고, 바꾸는 방법을 사용합니다.
            }
        }
    }
    
    for(int k=0; k<=9; k++){
        printf("%d ", s[k]);
    }
	
}

입력 : 2 10 9 8 7 4 5 6 1 3
출력 : 1 2 3 4 5 6 7 8 9 10