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

선택정렬이란?

선택정렬은 앞에서부터 쭉 탐색하면서 가장 작은 수를 찾습니다.(오름차순의 경우)

그리고 그 수를 (정렬되지 않은 부분의)맨앞의 수와 교체합니다.

이 과정을 정렬되지 않은 수가 1개 남을 때까지 반복하면 됩니다.

 

이 때 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다.

탐색은 정렬되지 않은 부분에 대해서만 이루어 집니다.

 

 

주황색 - 정렬된 부분

흰색 - 정렬되지 않은 부분

하늘색 - 정렬되지 않은 수 중 가장 작은 수

1. 정렬되지 않은 부분에서 가장 작은 수를 찾는다.
2. 정렬되지 않은 부분의 맨 앞의 수와 가장 작은 수를 교환(swap)한다.
3. 교환된 가장 작은 수는 정렬된 부분이 된다.
4. 정렬되지 않은 부분에서 위 과정을 반복하고, 모두 정렬되면 종료

 

시간복잡도

가장 작은 수를 찾는데 n-1, n-2, n-3, ...,1번 걸리므로

n-1+n-2+n-3+...+1 = n(n-1)/2

=O(n^2)

최선, 최악의 경우 모두 n^2의 시간복잡도를 가짐

 

 

소스코드(C++)

#include <iostream>

using namespace std;

void selection_sort(int arr[], int size){ //선택정렬

	int min;//최소 값의 index번호

	for(int i = 0;i<size-1;i++){
		min = i; //정렬되지 않은 부분의 첫번째 index
		for(int j = i;j<size;j++){
			if(arr[j]<=arr[min]){ 
				min = j; //현재 가장 작은 값보다 작으면 갱신
			}
		}
		swap(arr[i],arr[min]);//교환
	}
}

void swap(int &a,int &b){ //교환
	int temp = a;
	a = b;
	b = temp;
}

int main(){
	int arr[] = {4,3,1,6,2,5}; //정렬할 배열
	int size = sizeof(arr)/sizeof(int);//배열 크기

	selection_sort(arr,size);//선택정렬
	
	for(int i = 0;i<size;i++){ //배열 출력
		cout<<arr[i];
	}
}