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

선택 정렬

특징 (오름차순 기준)

0.  인간이 정렬할 때 본능적으로  사용하는 방법과 제일 유사 

     남아 있는, 섞여 있는 카드에서 제일 작은 숫자의 카드를 찾아서 이미 정렬된 배열 맨뒤에 위치시킨다.

1.  앞에서부터 뒤쪽으로 정렬되고, 정렬된 부분은 절대 변하지 않는다.

즉, 오름차순이므로 작은 수부터 정렬된다.

2. 선택 정렬의 비교 횟수는 최소값을 찾기 위해서 N(N-1)/2 정도, 교환 횟수는 많아야 N-1회 

즉, 비교 횟수 > 교환횟수

코드를 한번 봅시다.

static void select(int* src, int count) {
        int min;
        int minindex;
 
        for (int i = 0; i < count - 1; i++) {
            minindex = i; // 일단 시작점을 min으로 잡는다.
            min = src[i]; // 일단 시작점을 min으로 잡는다.
            for (int j = i + 1; j < count; j++) {
                if (min > src[j]) {
                    min = src[j];
                    minindex = j;
                    // j값을 증가시키며 
                    // 조건에 맞을 경우, min을 갱신한다.
                    // 원본 배열을 이 for문안에서는 갱신하지 않는다.
                }
            }
            src[minindex] = src[i];
            src[i] = min;
            printArray(src, count);
        }
        
    }

외부 for문은 각 단계에서 제일 작은 숫자가 들어가야할 위치를 한칸씩 이동시켜주는 역할을 하며

내부 for문은 관심 영역(이미 정렬된 영역에 대해 오른쪽)에서 제일 작은 숫자를 찾기 위해 한칸씩 이동시켜준다.

특징적인 것은 min, minindex라는 임시 변수를 사용했다는 점이다.

내부 for문에서 임시-최소값을 찾을([비교]를 통해서) 때마다 [교환]을 해주는 것이 아니라, min, minindex에 저장해둔다.그리고 내부 for문을 나오면, min, minindex를 사용하여 실질적인 [교환]을 실시한다.