선택정렬

선택정렬의 특징

1. 최솟값 선택 기반 정렬

인접한 두 원소만 비교하는 버블 정렬과 다르게, 매 라운드마다 남은 범위 전체를 훑어서 최솟값의 위치를 먼저 찾고, 그 다음에 현재 위치와 딱 한 번만 교환하는 방식이다. 비교는 멀리 떨어진 원소끼리도 하지만, 교환은 매 라운드당 최대 한 번 일어난다.

 

2. 시간 복잡도

바깥 루프가 n번 돌고, 안쪽 루프(최솟값 탐색)는 바깥 루프가 진행될수록 반복 횟수가 점점 줄어들어(n,n-1,n-2,...,1) 총 비교 횟수는 버블 정렬과 똑같이 등차수열의 합 공식에 의해 n(n-1)/2번이 된다. 빅오 표기법으로는 O(n²)이다. 다만 버블정렬과 결정적으로 다른 점은, 배열이 이미 정렬되어 있어도, 안쪽 루프를 끝까지 다 돌아야 최솟값 위치를 확신할 수 있어서 최선의 경우에도 O(n²)로 줄어들지 않는다는 것이다.

 

3.불안정 정렬이다.

값이 같은 두 원소가 있을 때, 최솟값을 찾아 먼 위치와 통째로 자리를 밥꾸는 과정에서 원래 순서가 뒤바뀔 수 있다.

 

4.제자리 정렬이다.

추가 배열이나 메모리 공간이 거의 필요없다. temp변수 하나로 교환만 하면 되니까 공간복잡도는 O(1)이다.

 

5. 실전성

실전성은 버블정렬보단 낫지만, 여전히 낮다. 같은 O(n²) 계열에선 삽입 정렬이 대부분의 경우 더 빠르지만, 선택 정렬은 교환(swap) 횟수가 라운드당 1번, 전체 최대로도 n-1번으로 압도적으로 적다는 장점이 있다. 그러나 큰 데이터셋에는 여전히 O(n log n)인 다른 정렬법을 사용한다.

 

6. 플래그

앞서 나는 버블정렬에서 플래그를 이용하여 루프 횟수를 줄이는 방식을 사용했다. 그러나 선택정렬에서는 이 방식을 사용할 수 없다. 그 이유는 "정렬이 끝났다는 확신"을 얻는 방식 자체가 다르기 때문이다.

버블정렬은 한 바퀴 돌면서 인접한 칸끼리 비교하며 스왑한다. 따라서 한 바퀴에서 스왑이 한 번도 발생하지 않았다는 것은, 그 자체로 이미 배열이 정렬되어 있다는 것을 증명해준다.

반면 선택정렬은 i번째부터 끝까지 중에서 최솟값의 위치를 찾는 과정이다. 이 최솟값이 진짜 최솟값인지 확신하려면, 남은 원소를 전부 다 비교해봐야만 한다. 배열이 이미 정렬되어 있어도 선택정렬 입장에서는 그 사실을 모르기 때문에, 매 라운드마다 마지막 칸까지 비교를 마쳐야만 "이게 최솟값이 맞다"는 확신을 얻을 수 있다. 그래서 이전 라운드에서 값이 갱신되지 않았다는 사실이, 다음 라운드의 비교를 생략할 근거가 되지 못한다.

정렬 과정

작성한 코드

#include <stdio.h>

int main() {
	int aList[5] = { 30, 40, 10, 50, 20 };
	int aListSize = sizeof(aList) / sizeof(int);
	int rotationCount = 0;

	for (int i = 0; i < aListSize; i++) {
		int temp = 0;
		int nMinIndex = i;
		for (int j = i; j < aListSize; j++) {
			if (aList[nMinIndex] > aList[j]) {
				nMinIndex = j; 
			}
		}
		temp = aList[i];
		aList[i] = aList[nMinIndex];
		aList[nMinIndex] = temp;
		++rotationCount;
	}

	for (int i = 0; i < aListSize; i++) {
		printf("%d\t", aList[i]);
	}
	printf("\nRotation Count : %d", rotationCount);

	return 0;
}