C언어로 배우는 자료구조 [선택정렬]

선택 정렬의 이해

선택 정렬(Selection Sort)는 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를

교환하는 방식으로 정렬한다. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리 교환을 한다.

그 다음 두번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환하고,그 다음에는 세 번째로 작은 원소를

찾아서 세 번째 원소와 자리를 교환한다. 이 과정을 반복하면서 정렬을 완성한다.

​

정렬되지 않는 원소 [5,4,3,2,1] 을 선택정렬을 이용하여 오름차순 하여 정렬하자.

​

1회전 [1,4,3,2,5]

2회전 [1,2,3,4,5]

​

2회전 만에 정렬이 완료 되었다.

​

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

​

#include <stdio.h>
//선택정렬 
void main(){
    int arr[5] = {5,4,3,2,1};
    int i,j,k;
    int tmp=0;
    int min=0;
    for(i=0;i<4;i++)
    {
        min = i;
        for(j=i+1;j<5;j++)
        {
           if(arr[min] > arr[j])
           {
                  min = j ; //가장 작은 값의 배열의 index 번호를 저장 
           }
        }
        tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    for(k=0;k<5;k++){
        printf(" [%d] ",arr[k]);
    }
} 
 
실행결과 : [1]  [2]  [3]  [4]  [5]

​

n개의 원소에 대한 선택 정렬은 n개의 메모리를 사용한다. 선택 정렬에서의 비교 횟수를 구해보면 1단계에서는 첫 번째 원소를

기준으로 n개의 원소를 비교하고 , 2단계에서는 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소를 비교하고 , 3단계에서는

세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소를 비교한다. 이러한 방법으로 i단계에서는 i번째 원소를 기준으로

n-i개의 원소를 비교하게 되므로 전체 비교 횟수는 다음과 같다. 2 / n(n-1)