[정렬] 선택정렬( Selection sort )

 

void SelectionSort(int A[], int n) // input Array, index size
{
	int i, j, MinIndex;
    for(i = 0; i<n-1;i++){
    	MinIndex = i;
        for(j = MinIndex + 1; j<n;j++){
        	if(A[MinIndex] > A[j])
            	MinIndex = j;
                }
        if(MinIndex != i) swap(A[i], A[Minindex]);
       }
}

알고리즘 설명

1. MinIndex 로 배열의 비교 기준을 변화시켜 비교

2. A[MinIndex] > A[j] 이면 기준 인덱스와 비교 인덱스와 비교 후 MinIndex 변경

3. 두번째 포문이 끝나고 MinIndex 값이 바뀌었다면 스왑

 

i번째 단계에서 항상 n-i회 비교수행

평균시간복잡도 = O(n2)

최악시간복잡도 = O(n2)

 

제자리성 : 제자리 정렬

- i,j,MinIndex 상수크기 메모리

 

불안정한 정렬

- B b a c > a b B c