선택 정렬

선택 정렬(Selection Sort)

---

 선택 정렬은 O($n^2$)의 복잡도를 가진 대표적인 알고리즘이다. 

비교 정렬이면서 제자리 정렬 방식으로, 한 번 돌 때마다 가장 큰 원소를 선택하여 배치한다는 의미이다.

 평균적으로 같은 성능을 보여준다는 특징이 있다.

 어찌보면 사람이 실제로 정렬하는 방식과 가장 유사하기 때문에 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 대단히 비효울적인 정렬 방식이므로 실제 개발에선 사용되지 않는다.

정렬 방법(오름차순)

---

 배열의 모든 원소를 모두 비교하여 그 중 가장 작은 값을 찾고, 찾아낸 값의 위치와 첫 번째 원소를 바꾸면 된다.

 처음 모든 원소를 비교하면 총 $n-1$회 비교하게 되는데, 한 번 수행했을 경우 가장 작은 원소가 가장 앞에 위치하게 되므로 다음 수행의 비교 횟수는 1회 줄어든다. 그러면 첫 수행 시 $n-1$회, 그 다음 수행 $n-2$회 $...$ 최종 수행 시 $1$회 비교하게 되어 총 $\frac{n(n-1)}{2}$회 비교한다.

▶ 과정을 순서대로 표현하면 다음과 같다.

1. $i=0$에서, 주어진 배열의 가장 작은 값을 찾고 $i$번째 원소와 교환한다.
2. 교환한 $i$번째 원소는 다음 비교에서 제외한다.
3. $i$를 $n-1$이 될 때까지 1씩 더하며 반복한다.

그림과 함께 수행 과정을 살펴보자.

위와 같이 8개의 원소가 임의의 순서로 저장된 배열이 있다.

우선은 8개의 원소 중에 가장 작은 $2$를 선택한다.

그리고 $2$가 저장된 3번 인덱스와 0번 인덱스를 교환한다.

위치가 잡힌 0번 인덱스는 제외하고 나머지 원소 중 가장 작은 $58$을 선택한다.

그리고 $58$이 저장된 7번 인덱스와 1번 인덱스를 교환한다.

후에 계속 반복하게 되면,

이 경우는 4번 인덱스의 $138$이 선택되었음에도 불구하고 4번 인덱스, 즉 자기 자신과 교환해야한다.

하지만 교환을 하거나 안 하거나 차이가 없기 때문에 문제는 없다.

이 교환을 수행하고 나면 정렬이 완료되어있지만,

 컴퓨터 입장에서는 나머지 원소 두 개가 정렬이 되었는지 확인할 방법이 없기 때문에 

실제로는 나머지 원소에 대해서도 선택 정렬을 수행한다.

이처럼 정렬이 된 것을 확인할 수 있다.

위에 설명한 것과 같이 실제로 원소가 정렬이 되어 있더라도 정렬 유무를 판별할 방법이 없기 때문에

모든 경우에 O($n^2$)의 시간 복잡도를 가지게 되므로 비효율적이다.

하지만 그림에서 보는 것과 같이 이해하고 구현하기 쉽기 때문에 매우 간단한 문제를 빨리 해결하기 위해선 사용해볼 만하다.

소스코드

---

 간단한 알고리즘인 만큼 소스코드 또한 간결한데, C언어를 사용하여 구현한 코드를 게시하여 보겠다.

#include<stdio.h>
#define LEN 8
#define INF 0xFFFFFFF
 
void Swap(int *a, int *b){ // 두 수를 바꾸는 함수
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void PrintArray(int *arr, int len){ // 배열 값들을 출력하는 함수
    for(int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
void Selection_Sort(int *arr, int len){ // 선택정렬
    for(int i = 0; i < len - 1; i++){
        int minIDX = i; // 가장 작은 수의 인덱스를 저장하고 있는 변수
        for(int j = i + 1; j < len; j++){
            if(arr[minIDX] > arr[j]) // 지금까지 가장 작은 인덱스의 값보다 j번째 인덱스가 저장한 값이 작으면
                minIDX = j; // 가장 작은 인덱스를 j로 바꾸어 줌.
        }
        Swap(&arr[i], &arr[minIDX]); // i이후로 가장 작은 값의 인덱스와 i번째 인덱스 교환
        PrintArray(arr, len);
    }
}
 
int main(){
    int arr[] = {68, 126, 1001, 2, 138, 338, 168, 58};
    Selection_Sort(arr, LEN);
    return 0;
}

 이 글은 제가 공부하면서 이해한 부분을 정리한 것입니다.

 틀린 부분이 있다면 댓글로 피드백 해주시고 도움이 되셨다면 추천과 공감 부탁드리겠습니다.

출처 : 나무위키(정렬 알고리즘)