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

 

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

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

 

1. 아직 정렬되지 않은 부분에서 가장 작은 요소 selection[i]를 선택

2. selection[i]와 아직 정렬되지 않은 부분의 첫번째 요소를 교환

3. n-1회 반복

 

배열 selection의 선택 정렬 과정

 

메서드 swap() : a[idx1] 과 a[idx2] 를 교환

매개변수 : int[] a, int idx1, int idx2

 

메서드 selectionSort() : 길이가 n인 배열 a를 선택 정렬

매개변수 : int[] a, int n

 

- 선택 정렬

void swap(int[] a, int idx1, int idx2) {
	int t = a[idx1];
	a[idx1] = a[idx2];
	a[idx2] = t;
}

void selectionSort(int[] a, int n) {
	for(int i = 0; i < n-1; i++) {
		int min = i;
		for(int j = i+1; j < n; j++) {
			if(a[j] < a[min]) {
				min = j;
			}
		}
		swap(a, i, min);
	}
}

 

 

 

 

선택 정렬 Selection Sort :

최선 = 평균 = 최악 = O(N^2)

불안정한 정렬