정렬 알고리즘(선택 정렬)

개요

일반적으로 알고리즘을 공부 할 때 가장 쉽게 먼저 접하는 문제는 ‘정렬(Sort)’문제라고 할 수 있다.

본 포스팅에서는 정렬 알고리즘 중에서도 선택정렬 을 구현하고 시간 복잡도를 알아 보도록 하겠다.

문제

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

1 10 5 8 7 6 4 3 2 9

SOL

문제를 해결하기 위해 “가장 작은 것을 선택하여 앞으로 보내기”를 이용할 수 있다.

위와 같은 방법을 우린 선택정렬 이라고 부르고, 한번 cpp 로 구현해보도록 하겠다.

구현

#include <iostream>

using namespace std; 

int main(void) {
	int i, j, min, index, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for(i = 0; i < 10; i++) {
		min = 9999;
		for(j = i; j < 10; j++) {
			if(min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	for(i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
	return 0;
}

출력 값

1 2 3 4 5 6 7 8 9 10

해설

위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.

여기서 중요한 것은 데이터의 개수가 N개일 때 총 몇 번의 비교연산이 이루어 지고 있는지 확인하는 것이다. 따라서 이를 식으로 표현한다면

N * (N + 1) 로 표현할 수 있으며, 이을 빅오 표기법으로 표현하면

O(N^2) 로 표현할 수 있다.

본 포스팅을 동빈나님의 블로그를 참고하여 작성되었습니다.