정렬 알고리즘 - 선택 정렬[ Selection Sorting ]

정렬 알고리즘 중 하나인 선택 정렬[ Selection Sorting ]에 대해 설명드리겠습니다~!

 

[선택 정렬이란??]

정렬 알고리즘 중 하나로 정렬이 되지 않은 데이터들을

선택한 하나의 데이터와 비교하면서 가장 작은 데이터를 앞으로 보내 정렬시키는 알고리즘입니다. 

 

 

 

[선택 정렬 예시]

5

4

6

3

1

위의 5, 4, 6, 3, 1의 데이터 값들을 가장 작은 숫자가 앞으로 오게 선택 정렬을 시켜보겠습니다.

 

첫 번째 : 가장 작은 데이터 값인 1을 가장 앞으로 보내고

가장 앞에 있는 데이터 5는 1이 있던 자리로 옮겨줍니다.

1

4

6

3

5

 

: 첫 번째 칸의 데이터 값을 제외하고 나머지 데이터들 중 가장 작은 값인 3을

두 번째 위치해있는 4와 자리를 바꾸어줍니다.

1

3

6

4

5

 

세 번째 : 첫 번째 두 번째의 데이터 값을 제외하고 나머지 데이터들 중 가장 작은 값인 4를

세 번째 위치해있는 6과 자리를 바꾸어줍니다.

1

3

4

6

5

 

네 번째 : 첫 번째, 두 번째, 세 번째 데이터 값을 제외한 나머지 데이터들 중

가장 작은 값인 5를 네번째 데이터 값 6과 자리를 바꾸어줍니다.

1

3

4

5

6

 

그러면 이와 같이 가장 작은 데이터 값이 앞으로 오는 선택 정렬을 할 수 있습니다.

 

 

 

 

[선택 정렬 코드]

#include <stdio.h>
 
int main()
{
    int i, j, min, index, temp;
 
    int arr[5] = { 5, 4, 6, 3, 1 };
 
    for (i = 0; i < 5; i++) {
        min = 999;
        for (j = i; j < 5; j++) {
            if (min > arr[j]) {
                min = arr[j];
                index = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
 
    printf("정렬 후 데이터 값\n");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
}

1. 주어진 데이터 값중 가장 작은 값을 찾는다.

2. 그 값을 맨앞에 위치한 값과 교환한다.

3. 나머지 데이터도 똑같이 진행해줍니다.

 

 

 

 

[정리]

선택 정렬은 데이터 값들을 모두 비교해 가장 작은 값의 위치를 기억해 두었다가

가장 작은 값과 맨앞의 데이터를 교환하는 방식입니다.

 

전체 데이터 수 n개 중에서 가장 작은 값을 첫 번째 데이터와 교환합니다.

나머지 데이터 n-1개 중 가장 작은 값을 두번째 데이터와 교환합니다.

이와 같은 방법을 정렬이 완성될때 까지 진행합니다.

결과 적으로 선택 정렬은 n * (n+1) / 2 정도의 연산을 수행한다고 할 수 있습니다.

 

이처럼 선택 정렬은 가장 작은 데이터 값을 앞으로 보내면

그 데이터는 더 이상 비교하지 않아도 되기 때문에 이전에 포스팅했던

버블 정렬보다는 조금 더 효율적이고 간편한 방법이라고 할 수 있습니다.