[알고리즘] 1_3. 선택 정렬(Selection Sort)

1. 정의

선택 정렬(Selection Sort)이란, 현재 선택된 데이터 이후의 정렬 되지 않은 데이터 중에서 가장 작은(혹은 가장 큰) 데이터를 선택해 현재의 데이터와 위치를 교환하는 방식으로 정렬되는 방식이다. 

2. 설명

PASS 1

우선 가장 앞의 데이터가 선택되게 된다. 그리고 그 데이터 이후를 탐색해 가장 작은 데이터를 찾는다. 최소 값의 데이터를 찾았다면, 두 데이터의 위치를 교환해준다. 예시의 데이터에서는 4 와 1 의 위치를 교환해주게 된다.

PASS 2

두 번째에서는, 2 가 선택되게 된다. 선택된 이후의 데이터에서 2 보다 작은 값은 존재하지 않으므로, SWAP 과정이 존재하지 않고 완료될 것이다.

PASS 3

PASS 3에서도 PASS 1, PASS 2와 동일한 방법을 시행한다.

PASS 4

PASS 5

PASS 6

정렬이 완료된 모습이다.

3. 코드

1) 선택정렬

1 2 3 4 5 6 7 8 9

for(i=0;i<Len;i++){//Len은 정렬할 데이터 수     for(j=i+1;j<Len;j++){         if(data[i]>data[j]){             int temp=data[i];             data[i]=data[j];             data[j]=temp;         }     } } Colored by Color Scripter

cs

2) 개선된 선택정렬

for(i=0;i<Len;i++){//Len은 정렬할 데이터 수
    int minindex=i;
    int min=data[i];
    for(j=i+1;j<Len;j++){//find minimum
        if(data[j]<min){
            min=data[j];
            minindex=j;
        }
    }
    /*swap*/
    int temp=data[i];
    data[i]=data[minindex];
    data[minindex]=temp;
}

선택정렬과 개선된 선택정렬과 다른 점은 Swap의 횟수이다. 앞선 기존의 선택정렬은 PASS 한 번당 한 번 이상의 Swap 과정이 존재할 수 있다. 하지만, 개선된 선택정렬의 경우, Minimum 값의 index를 찾아 현재 선택된 데이터와 Minimum 두 값만 한 번 Swap을 하기 때문에, 효율적일 수 있다.

다른 정렬 알고리즘 보기