[알고리즘] 선택정렬(Selection Sort)

선택정렬(Selection Sort)

선택정렬(Selection Sort)은 데이터 집합에서 왼쪽 인덱스부터 정렬될 값과 해당 위치에 있는 값을 교환하며 정렬을 수행한다.

 

 - 이미 제자리에 있어도 비교를 수행한다.

 - O(n²)의 시간 복잡도를 갖는다.

 

 

기본 동작 과정

배열에 저장된 값을 오름차순 정렬으로 할 때 다음과 같은 동작 과정을 수행한다.

 

 ① 배열의 왼쪽부터 배열의 끝까지 비교를 수행한다.

 

 

 

 

 

 ② 비교를 수행하던 중 비교하는 값이 비교할 값 보다 작은경우 해당 인덱스를 기억한다.

 

 

 

 

 

 

 ③ 배열의 끝까지 비교를 수행했을때 기억해둔 인덱스의 요소 값과 비교하는 값을 교환한다.

 

 

 

 

 ④ 배열의 마지막 인덱스까지 비교하면 맨 첫 번째 값은 정렬된 상태이다.

 

 

1회

 

 

 

 ⑤ 모든 값이 정렬될 때까지 과정 ①, ②, ③ 반복

 

 

2회

 

 

 

3회

 

 

 

최종

 

※ n-1번 반복했을 때 정렬이 끝난다.

 

 

알고리즘 분석

선택정렬의 복잡도는 항상 O(n²)의 시간 복잡도를 갖는다.

 

최선·최악의 경우

 - 비교 횟수 : n(n - 1) / 2

 - 이동 횟수 : 3(n - 1)

 

선택 정렬 소스 코드

#include <stdio.h>

#define SWAP(x, y, t) ( ( t ) = ( x ), ( x ) = ( y ), ( y ) = ( t ) )

void Print(int arr[], int length) {
	printf("---- * Selection Sort 결과 * ----\n");
	for (int i = 0; i < length; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n---------------------------------\n");
}

// 오름차순 선택 정렬
void SelectionSort(int arr[], int length) {
	int temp;

	for (int i = 0; i < length - 1; i++) {
		int least = i;
		for (int j = i + 1; j < length; j++)
			if (arr[j] < arr[least])
				least = j;
		SWAP(arr[i], arr[least], temp);
	}
}

void main() {
	int data[5] = { 3, 1, 4, 5, 2 };
	int length = sizeof(data) / sizeof(int);

	SelectionSort(data, length);
	Print(data, length);
}