선택정렬 (feat. Selection Sort)

 

 

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 

선택정렬은 가장 직관적인 정렬 방법입니다.

배열 10개가 있다고 가정해봅시다.

아래는 오름차순을 기준으로 기재하였습니다.

 

1. 배열[0]을 기준으로 배열[1] ~ 배열[9] 중 최소값이 있는 인덱스를 찾습니다. 그리고 해당 인덱스의 값과 배열[0]의 값을 서로 swap 합니다. (찾은 인덱스가 없다면 배열[0]과 배열[0]을 서로 swap 할 수도 있고 swap 자체를 하지 않아도 됩니다.)
2. 다음으로 배열[1]을 기준으로 배열[2] ~ 배열[9] 중 최소값이 있는 인덱스를 찾습니다. 그리고 해당 인덱스의 값과 배열[1]의 값을 서로 swap 합니다. (찾은 인덱스가 없다면 배열[1]과 배열[1]을 서로 swap 할 수도 있고 swap 자체를 하지 않아도 됩니다.)
3. 배열[8]이 기준이 될때까지 위 행위를 반복합니다.

반응형

 

위와 같은 방법으로 선택정렬을 구현할 수 있습니다.

모든 배열의 값들을 비교하므로 브루트포스 알고리즘 기법이라고 할 수 있습니다.

 

선택정렬을 코드로 구현하면 아래와 같습니다.

 

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <random>
#include <algorithm>
using namespace std;
void selection_sort(int* arr, register int length){
    for(register int i = 0; i < length - 1; ++i){
        register int min_idx = i;
        for(register int j = i + 1; j < length; ++j)
            if(arr[j] < arr[min_idx])
                min_idx = j;
        swap(arr[i], arr[min_idx]);
    }
}
int main(){
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<int> range(0, 10000);
    int arr[20];
    for(auto& v : arr)
        v = range(mt);
    cout << "before : ";
    for(auto& v : arr)
        cout << v << " ";
    cout << "\n";
    selection_sort(arr, sizeof(arr) / sizeof(arr[0]));
    cout << "after : ";
    for(auto& v : arr)
        cout << v << " ";
    return 0;
}
// *&)*@*

 

선택정렬 (위키백과)