알고리즘 기초 및 선택 정렬(Selection Sort)

문제

 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
 1 5 8 10 7 6 3 2 9 4

 

위와 같은 문제에서 가장 직관적인 접근은 숫자들을 정렬하는 것입니다.

정렬알고리즘에는 정말 많은 종류들이 있습니다.

 

알고리즘 종류

• Selection sort (내부 : 교환)
• Bubble Sort (내부 : 교환)
• Quick Sort (내부 : 교환)
• Insertion Sort (내부 : 삽입)
• Shell Sort (내부 : 삽입)
• Merge Sort (내부 : 병합)
• Heap Sort (내부 : 선택)
• Radix Sort (내부 : 분배)

 

또한 이 알고리즘 마다 시간 복잡도가 다른데,

시간복잡도는 아래와 같습니다.

 

시간복잡도

O(n²) : Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Quick Sort

O(n log n) : Heap Sort, Merge Sort

O(kn) : Radix Sort (k는 자릿수, 자릿수가 적은 4바이트 정수에서나 제대로 된 성능을 낼 수 있다는 제약조건이 있다.)

 

하지만 이 알고리즘 중에서 한 번 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘을 선택하도록 하겠습니다.

이 알고리즘을 바로 '선택 정렬'이라고 합니다.

 

선택정렬 알고리즘

#include <stdio.h>

int main(void) {
	int i, j, min, index, temp;
	int array[10] = {1, 5, 8, 10, 7, 6, 3, 2, 9, 4 };
	for(i = 0; i < 10; i++) {
		min = 99999;
		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;
}

 

  위의 소스코드는 min에 최소값을 넣기위해 큰 숫자를 넣은 변수이고, temp는 두 문자열의 위치를 서로 바꾸기 위해 사용한 변수입니다.

 

 

위와 같이 정상적으로 실행 되었음을 알 수 있습니다. 자료구조와 알고리즘에서 가장 중요한 점은 데이터의 개수가 N개 일 경우, 총 몇 번의 비교 연산을 하는지 아는 것입니다. 선택 정렬은 대략 N * (N + 1 ) / 2번 가량의 연산을 수행해야 하고 이를 컴퓨터에서는 가장 큰 차수인 N^2만 보고 O(N^2)라고 표현합니다.

 

선택 정렬의 시간복잡도 O(N^2)

반복문을 몇번 사용하였는지, 입력값은 어떻게 되는 지를 통해 대략적으로 우리가 작성한 코드의 실행시간이 얼마나 걸리는지를 알아보는 것이 중요합니다. 즉, 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 하며, 시간복잡도를 통해 수행 시간을 파악할 수 있는 것이 중요합니다.