(2) 선택 정렬법(Selection Sorting)

 앞의 리스트 5의 정렬법을 가만히 관찰해 보면 간단한 방법으로 수행 속도를 향상시킬 수 있는 것
을 알 수 있다. 방법을 읽기 전에 잠시만  여러분 스스로 생각을 해보기 바란다. 약간의 힌트를 준
다면, 반복해서 수행되는 부분을 주의해서 살펴보라.

 리스트 5의 예를 가만히 살펴보면, 옆의 값과  비교 후에 바로바로 값을 교환하는 것을  알 수가
있다. 이렇게 바로 교환하는 방법은 교환 횟수를 상당히 많게 만든다. 한번의 교환을 하기 위해서
는 3번의 치환문이 사용된다. 이것을 다음과 같이 바꾸어 보면 어떨까?

 리스트 6의 방법은 앞의 단순 정렬법과는 달리 일단 정렬되지 않는 값들 중에 가장 큰 값이 있는
위치를 알아낸 후 한 번의 교환에 의해 그 값이 정렬되지  않는 값의 맨 뒤로 옮겨지게 된다. 이 방
법은 자료의 교환 횟수를 앞의 방법보다 상당히 감소시킨다. 따라서 교환해야 할 자료의 크기가
클수록 효과는비례해서 증가하게 된다.

(리스트 6) 선택 정렬법을 사용한 예
void Select_Sort(int *a,int last_item)
{
        int loop1,loop2;
        int temp;
        int max_item;
        for (loop1=0;loop1<last_item;loop1++)
        {
                max_item=0;
                for (loop2=0;loop2<(last_item-loop1);loop2++)
                {
                        if (a[max_item]<a[loop2+1])
                                max_item=loop2+1;
                        temp=a[max_item];
                        a[max_item]=a[max_item-loop1];
                        a[last_item-loop1]=temp;
                }
        }
}