티끌 모아 태산

기본개념

• 정렬할 키가 배열 A[0:n-1] 에 저장되어 있다고 가정할 때
•  가장 작은 키, 둘째로 작은 키, 셋째로 작은 키 등을 순서대로 선택하여 배열의 원소를 재배치시키면서 배열을 정리한다.
•  n개의 키 중에서 가장 작은 것을 찾아 그 키와 첫째 키인 A[0] 와 자리바꿈 한다.
•  다음에는 남아 있는 키들 중에서 가장 작은 키를 찾아 그 원소와 A[1] 의 자리를 바꾼다.
•  i번째 단계에 이르면 A[0:i-2] 에는 가장 작은 i-1 개의 키가 이미 순서대로 정렬되어 있다.
•  i번째 단게에서는 남아 있는 n-i+1개의 키 중에서 가장 작은 것을 찾아 A[i-1]와 바리를 바꾼다.
• 이러한 단계를 n-1회 거쳐 배열 전체를 정리한다. 

시간복잡도 O(n^2) 

공간복잡도 O(n)

알고리즘

void SelectionSort (int A[ ], int n) {
/* 입력 : A[0:n-1] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
   출력 : A[0:n-1] - 정렬된 배열. */
   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]);
   }
}   

• 선택 정렬은 간단하며 레코드 수가 작은 경우에 효율적, 정렬 과정에서 모든 키는 자신의 자리를 찾은 후에는 자리 이동을 하지 않는다.
• 키의 비교 횟수를 살펴보면, 가장 작은 키를 고르는 데 n-1 , 두 번째로 작은 키를 고르는데  n-2회의 비교를, 일반적으로 i번째 작은 키를 고르는 데 n-i 회의 비교를 하게 되므로
• (n-1) + (n-2) + ... +1=n(n-1)/2 회의 키 비교를 하게 된다.
• i번째 단계에서는 항상 n-i 회의 비교를 하므로 알고리즘의 실행 시간은 입력 자료의 순서에 민갑하지 않다.
• 3~4개의 변수 외에는 별도의 메모리 공간을 차지하지 않는 제자리 정렬 이다.

참고 : 알고리즘 - 이한출판사