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

선택정렬은 모든 레코드가 key값으로 표현되어, 한 원소와 나머지 모든 원소를 비교하는 정렬이다.

void SelectionSort(int A[], int n){
    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])
            }
        }
    }
}

• i번째 단계에서 항상 n-1회 비교수행 => 복잡도는 입력자료 순서와 무관하다.
• 평균시간 복잡도=O(n^2) 

• 최악시간 복잡도=O(n^2)
  • 선택정렬의 경우 데이터의 내요ㅛㅇ과 관계없이 항상 마지막 단계까지 모든 비교가 이루어지기 때문에 평균 시간복잡도 == 최악시간복잡도이다. 
• 제자리성 : 제자리 정렬  (주어진 메모리 공간 외에 추가적으로 사용하는 (상수크기) 메모리가 없는 정렬)
• 안정성 : 불안정한 정렬 (정렬후에 같은 값인 요소의 순서가 보장되지 않는 정렬방식) 
  • 인접한 요소와 스와칭이 일러나면 대부분 안정한 정렬이다.(떨어져있는 요소와 스와핑이 일어나면 불안정할 가능성 99%)