25.03.19 / 선택 정렬(Selection Sort)

정렬(Sorting)이란 정해진 기준에 따라 데이터를 순서대로, 그리고 체계적으로 정리하는 알고리즘이다. 예를 들어 가격 비교 사이트는 가격, 평점, 출시일 등을 기준으로 상품을 오름차순/내림차순으로 정렬하여 고객의 선택을 돕고, 대학은 학생들의 입시 성적을 정렬해 합격 여부를 가려낸다. 책을 제목 순으로 책장에 꽂는 것, 시험 성적을 높은 점수 순으로 배열하는 것, 우유를 유통기한이 임박한 순으로 진열하는 것 모두 정렬이라 볼 수 있다.

 

그렇다면 우리는 왜 정렬을 할까? 정돈된 환경을 만들기 위해서일 수도 있지만, 궁극적인 목적은 물건이나 데이터를 쉽게 찾고자 하는 데 있다. 다시 말해, 정렬의 목적은 '탐색'에 있는 것이다. 책을 책장 안에 기준을 나눠 꽂아 두는 것은 나중에 찾고자 하는 책을 빠르게 찾기 위해서이고, 우유를 유통기한이 임박한 순으로 정렬하는 이유는 손님으로 하여금 유통기한이 다 되어가는 우유를 먼저 골라가도록 하기 위해서이다.

 

정렬 알고리즘 역시 데이터를 가지런히 나열하는 것 자체가 목적이 아니라 데이터를 빠르고 쉽게 찾을 수 있도록 하는 것이 목적이다.

 

최초의 컴퓨터로 알려진 ENIAC은 포탄의 사표를 계산할 목적으로 개발되어 정말 계산만 할 수 있었다. 본래 기억 능력은 가지지 않았다는 것이다. 존 폰 노이만이 설계를 개선한 후부터 컴퓨터는 진흙판이나 종이가 수행하던 정보 기록 임무를 수행할 수 있게 되었고, 얼마 지나지 않아 계산기의 역할뿐 아니라 엄청난 정보 기록 장치로서의 역할을 톡톡히 해내게 되었다. 그러나 기술이 발달함에 따라 컴퓨터가 저장하고 처리해야 할 데이터와 정보도 크게 늘어났다.

 

그래서 데이터 처리에 관한 여러 가지 기술이 과학자와 엔지니어에 의해 연구되었는데, 그중 하나가 정렬 알고리즘이다.

 

이번 포스팅에선 그 중 선택 정렬에 대해 알아보겠다. 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞으로 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교하는 것이다.

 

아래의 코드를 보며 천천히 과정을 따라가보자.

void SelectionSort(int _arr[], int _len) {
	if (_arr == NULL) return;

	// 3. _len - 1 만큼 1, 2 항목을 반복
	for (int j = 0; j < _len - 1; ++j) {
		// 1. 가장 작은 값을 가진 인덱스 찾기
		int minIdx = j;
		for (int i = j + 1; i < _len; ++i) {
			if (_arr[minIdx] > _arr[i]) {
				minIdx = i;
			}
		}
		// printf("Min : [%d] %d\n", minIdx, _arr[minIdx]);
		// 2. 제일 앞 인덱스와 값 교환
		int tmp = _arr[minIdx];
		_arr[minIdx] = _arr[j];
		_arr[j] = tmp;
		printf("Swap : [%d] <-> [%d]\n", minIdx, j);

		PrintAll(_arr, _len);
		printf("\n");
	}
}

 

배열 이름과 길이를 입력받아 선택 정렬하는 SelectionSort 함수를 만들었다. 배열 주소가 NULL이면 함수를 종료하고 반환한다. 이중 반복문을 사용해 첫 번째로 배열에서 가장 작은 값을 가진 인덱스를 찾는다. 외부 for문에선 j값(첫 실행이라 0)을 minIdx에 저장하고 내부 for문의 i를 배열이 끝날 때까지 늘려가며 _arr[i]를 검사해 _arr[i]가 _arr[minIdx]보다 작은 인덱스가 있으면 ifmf minxIdx에 대입한다. 내부 반복문이 끝나면 j번째 인덱스(첫 반복에서 제일 앞의 인덱스)와 _arr[minIdx]의 값을 바꾼다.

 

그 후엔 j값을 1, 2... 이런 식으로 늘려가며 작은 값을 점점 앞으로 오게 반복한다. 외부 반복문이 모두 종료되면 배열이 작은 수부터 큰 수까지의 순서로 정렬 된 상태가 된다.

 

값을 출력해보자. 값을 출력하는 PrintAll 함수는 이번 글에서 중요한 내용이 아니라 따로 다루지 않았다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void SelectionSort(int _arr[], int _len);
void PrintAll(int _arr[], int _len);

int main() {
	// 정렬(Sort, Sorting)
	// 선택 정렬(Selection Sort)
	// Big-O Notation
	int arr[10] = { 0 };
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 10; ++i) {
		arr[i] = rand() % 50;
	}
	
	PrintAll(arr, 10);

	SelectionSort(arr, 10);

	PrintAll(arr, 10);

	return 0;
}

void SelectionSort(int _arr[], int _len) {
	if (_arr == NULL) return;

	// 3. _len - 1 만큼 1, 2 항목을 반복
	for (int j = 0; j < _len - 1; ++j) {
		// 1. 가장 작은 값을 가진 인덱스 찾기
		int minIdx = j;
		for (int i = j + 1; i < _len; ++i) {
			if (_arr[minIdx] > _arr[i]) {
				minIdx = i;
			}
		}
		// printf("Min : [%d] %d\n", minIdx, _arr[minIdx]);
		// 2. 제일 앞 인덱스와 값 교환
		int tmp = _arr[minIdx];
		_arr[minIdx] = _arr[j];
		_arr[j] = tmp;
		printf("Swap : [%d] <-> [%d]\n", minIdx, j);

		PrintAll(_arr, _len);
		printf("\n");
	}
}

void PrintAll(int _arr[], int _len) {
	if (_arr == NULL || _len <= 0) return;
	for (int i = 0; i < _len; ++i) {
		printf("[%d] - ", _arr[i]);
	}
	printf("(%d)\n", _len);
}

실행 결과

[18] - [43] - [28] - [35] - [20] - [41] - [6] - [26] - [12] - [49] - (10)

Swap : [6] <-> [0]
[6] - [43] - [28] - [35] - [20] - [41] - [18] - [26] - [12] - [49] - (10)

Swap : [8] <-> [1]
[6] - [12] - [28] - [35] - [20] - [41] - [18] - [26] - [43] - [49] - (10)

Swap : [6] <-> [2]
[6] - [12] - [18] - [35] - [20] - [41] - [28] - [26] - [43] - [49] - (10)

Swap : [4] <-> [3]
[6] - [12] - [18] - [20] - [35] - [41] - [28] - [26] - [43] - [49] - (10)

Swap : [7] <-> [4]
[6] - [12] - [18] - [20] - [26] - [41] - [28] - [35] - [43] - [49] - (10)

Swap : [6] <-> [5]
[6] - [12] - [18] - [20] - [26] - [28] - [41] - [35] - [43] - [49] - (10)

Swap : [7] <-> [6]
[6] - [12] - [18] - [20] - [26] - [28] - [35] - [41] - [43] - [49] - (10)

Swap : [7] <-> [7]
[6] - [12] - [18] - [20] - [26] - [28] - [35] - [41] - [43] - [49] - (10)

Swap : [8] <-> [8]
[6] - [12] - [18] - [20] - [26] - [28] - [35] - [41] - [43] - [49] - (10)

[6] - [12] - [18] - [20] - [26] - [28] - [35] - [41] - [43] - [49] - (10)

 

랜덤 난수를 생성해 배열에 저장해 그 배열을 선택 정렬한 결과를 볼 수 있다.