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

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 
알고리즘의 동작에 대한 분석 및 구현 코드의 설명.

Selection Sort _ 선택 정렬

가장 작은 것을 선택해서 제일 앞으로 보내기 .

선택 정렬은 정렬하기를 원하는 원소를 찾고 그것의 위치를 찾아 바꿔주는 원소 교환을 사용하여 정렬을 수행한다. 이에 따르면 가장 작은 원소는 첫번째 위치로, 그 다음 작은 원소는 두번째 위치로 들어가게 된다. 이러한 동작을 계속 반복하는 것을 선택 정렬이라고 한다.

선택 정렬 알고리즘은 n개의 원소 각각에 대해 n-1번의 비교를 해야한다. 따라서 비교 연산 횟수는 (𝑛(𝑛−1))/2 이고, 대입 연산 횟수는 3(𝑛 − 1) 이므로, 선택 정렬 알고리즘의 worst case 시간 복잡도는 𝑂(n^2)이다. 선택 정렬 알고리즘은 for문을 도는 동안 정렬이 이루어지는 것은 단 한번 뿐이다. 

따라서 작은 key와 큰 데이터를 가진 시퀀스를 정렬하는데 적합하며, 입력 자료 순서에 민감하지 않다. 

하지만 이미 정렬되어 있는 데이터가 들어온다면, 이미 정렬이 되어있음에도 불구하고 정렬이 이뤄지기 때문에 worst case가 된다.또한 선택 정렬 알고리즘은 추가 저장 장소를 사용하지 않기 때문에 in-place 정렬이며, 동일한 키 값이 있을 때 위치가 유지 되지 않으므로 stable 하지 않은 알고리즘이다.

 

Implementation

Swap 함수

모든 정렬 알고리즘에서 Swap 모듈을 사용하므로, 함수화 하여 사용한다. 

동적 배열의 주소 값과 정수 값 두개를 인자로 받고 첫번째 인자 a 와 두번째 인자 b를 index 로 하는 배열의 두 값을 바꿔주는 함수이다. 

void Swap(int* arr, int a, int b){
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

Selection Sort

Selection Sort 함수는 인자로 동적 배열의 주소 값과 배열의 크기, 그리고 배열의 안의 성분들의 범위 값을 받는다. 이때 범위 값은 임의로 배열의 크기 X10으로 메인함수에서 선언해 두었다. 이 값을 함수 안에서 첫번째 for 문을 돌 때 Min 값으로 설정하였는데, 이는 가장 작은 값을 기준으로 정렬하는 선택 정렬을 함에 있어 가장 클 수 밖에 없는 range 값으로 설정한 것이다. ( 임의로 설정 가능하다. ) 

정렬 함수는 배열의 0번째 인덱스부터 n-1번째 인덱스까지 for문을 통해서 가장 작은 인덱스부터 작은 숫자로 채워지게 된다. 이때 n-1번쨰 인덱스 까지만 하는 이유는 마지막 원소는 그 전의 for문으로 인해 정렬이 완료 되었기 때문이다. 작은 값을 찾아가는 과정은 두번째 for문을 돌면서 Min 값과 현재 인덱스 값을 비교하며 가장 작은 값을 찾아가게 된다. Min값은 두번째 for문을 돌면서 새롭게 갱신되기도 한다. 

Selection 함수는 메인함수에서 호출되며, Selection 정렬을 시작하고, 실행시간을 측정한다. 

과제에 주어진 함수 별 실행시간을 측정하기 위해 ctime 라이브러리와 chrono 라이브러리를 사용하였다. Chrono는 시간을 Nano second 단위 까지 측정해 줄 수 있다. 이를 이용하여 실행 시간을 측정하고 nanosecond 단위로 출력하게 하였다. 

 

class SelectionSorter{
public:
	void SelectionSort(int* arr, int n, int range){
		int min, index;
		for(int i = 0; i<n; i++){
			min = range; //일단 min 값을 저장한다. 
			for(int j=i; j<n; j++){//i for문을 돌면서 앞자리 부터 작은 숫자로 채워진다. 
				if(min > arr[j]){//min 값보다 현재 값이 작다면 
					min = arr[j]; index = j; //현재값을 min 값으로 저장하고, 인덱스를 저장한다. 
				}
			}
			Swap(arr, i, index);
		}
	}
};
void Selection(int* arr, int n, int range){ //Selection Sort
	SelectionSorter sls; //Selection Sorter Class 
	steady_clock::time_point start, end; nanoseconds result; //chrono를 이용하여 실행시간 측정 
	start = steady_clock::now(); //steady_clock timer가 시작

	sls.SelectionSort(arr, n, range); //Selection Sort. 

	end = steady_clock::now(); result = end - start; //timer 끝
	cout<<"1. Selection Sort              : "<<result.count()<<"ns"<<endl; //알고리즘 실행시간 출력
}