알고리즘 - 정렬 1.1 선택 정렬

선택 정렬의 정의

: 입력 배열에서 가장 작은 값부터 순서대로 선택해서 나열하는 방식

 

선택 정렬의 처리 과정

 

int SelectionSort(A[], n){
	int tmp = 0;
	for(i=0; i < n-1; i++){ // n(-1)회 반복
    	min = i;
        for(j=i+1; j < n; j++){
        	if(A[min] > A[j]) min = j; //A[i..n-1]에서 최솟값 찾기
        }
        tmp = A[i] // 최소값과 A[i]의 위치 교환
        A[i] = A[min]
        A[min] = tmp
    }
    return A
}

 

성능

(n - 1) + (n - 2) + ... + 1 = n(n-1) / 2  => O(n^2)

 

특징

- 입력 데이터의 선수에 민감하지 않음 -> 입력 데이터의 상태와 상관없이 항상 동일한 성능을 가짐

- 제자리 정렬 알고리즘

: 입력 배열 A[] 이외에 상수 개의 저장 공간(예:  i, j, min, tmp)만 필요

- 안정적이지 않은 정렬 알고리즘

 

선택 정렬

- 불안정 알고리즘

- 제자리 정렬 알고리즘

- 성능 => O(n^2)