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

개요

선택정렬 알고리즘은 정렬되지 않은 부분배열에서 가장 작은 원소를 찾아 알맞은 위치에 삽입하고 이를 반복하여 배열 전체를 정렬하는 알고리즘이다.

 

위의 자료에서 정렬된 부분배열은 빨간색, 정렬되지 않은 부분배열은 검은색으로 표시했다. 

정렬되지 않은 부분배열을 순회해 가장 작은 key 값을 찾아, 알맞은 위치의 원소와 위치를 바꾼다.

이를 반복하면 전체 배열을 정렬할 수 있다.

---

코드

void Selection_Sort(int arr[], int size){
	int key, index;
	for(int i=0;i<size-1;i++){		// 큰 for문
		key = arr[i]; index = i;
		for(int j=i+1;j<size;j++){	// 작은 for문
			if(key > arr[j]){
				key = arr[j];
				index = j;
			}
		}
		arr[index] = arr[i];
		arr[i] = key;
	}
}

함수의 매개변수로 배열과 배열의 크기를 받는다.

배열의 크기가 n일 때, n-1번만 정렬해도 마지막 원소는 자동으로 정렬되기 때문에, 큰 for문은 (배열의 크기 - 1)번 반복하도록 설정했다.

정렬되지 않은 부분배열에서 가장 작은 값인 key값을 찾는 작은 for문은, 정렬되지 않은 부분배열이 시작하는 인덱스부터 배열의 끝까지 반복하도록 설정했다.

이후 key값의 값과 인덱스를 저장하고, 작은 for문을 빠져나와 key값을 알맞은 위치에 삽입 후, 다음 key값을 찾는 과정으로 넘어간다.

---

실행 결과

main 함수에 이것저것 추가해주고 코드를 돌려보면 다음과 같이 잘 작동하는 것을 볼 수 있다.

 

---

분석

• 선택정렬 알고리즘의 수행시간을 $ \Theta $-표기법으로 나타내면 $ \Theta(n^2) $ 이다.