[알고리즘] 정렬-선택정렬(selection sort)

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

선택정렬이란

기본 정렬 알고리즘 중 하나인 선택정렬에 대해 알아보겠습니다.

선택 정렬(selection sort)은 구현이 간단하고 O(n^2)의 시간복잡도를 가지는 정렬 알고리즘 중 하나입니다.

이 알고리즘의 기본 아이디어는 아직 정렬되지 않은 부분에서 가장 작은 (또는 가장 큰) 요소를 찾아서 정렬된 부분과 교환하는 것입니다. 이러한 과정을 반복하면서 전체 배열을 정렬합니다. 선택 정렬의 동작 방식은 다음과 같습니다:

선택정렬 과정, 출처: 위키백과

 

1. 주어진 리스트 중에 최소값을 찾습니다.

2. 그 값을 맨 앞에 위치한 값과 교체합니다.

3. 맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체합니다.

4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복합니다.

 

선택 정렬은 간단하고 이해하기 쉽지만, 다른 정렬 알고리즘에 비해 비효율적입니다.

선택 정렬의 시간 복잡도는 항상 O(n^2)입니다.

따라서 데이터의 크기가 크거나 성능이 중요한 경우에는 다른 정렬 알고리즘을 사용하는 것이 더 좋습니다.

 

선택정렬 코드 (C++)

void selection_sort(int arr[], int len){
    int minIndex, temp;
    for(int i=0; i<len; i++){
        minIndex = i;
        for(int j = i+1; j<len; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

 

테스트 코드

int main() {
    int arr[] = {20, 30,10,21,5,39,2};
    int len = sizeof(arr)/ sizeof(arr[0]);

    cout<<"before selection :"<<endl;
    for(int i=0; i<len; i++){
        cout << arr[i] <<" ";
    }

    selection_sort(arr, len);
    cout<<"\nafter selection :"<<endl;

    for(int i=0; i<len; i++){
        cout << arr[i] <<" ";
    }

    return 0;
}

 

테스트 결과

before selection :
20 30 10 21 5 39 2
after selection :
2 5 10 20 21 30 39