[Algorithm/C++] 선택 정렬(Selection Sort) - 선택하여 교환

 

1. 설명

 

선택 정렬(Selection Sort)란 리스트를 순차적으로 반복하면서 해당 위치에 해당하는 값을 탐색 후 선택하여 교체함으로써 정렬을 하는 정렬 방법 중 하나이다.

 

 

동작 예시 (출처: https://visualgo.net/en/sorting)

 

동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다.

 

 

따라서 탐색을 통하여 리스트에서 가장 작은 값의 인덱스를 선택한 후 첫 번째에 있는 값과 교환을 한다. 이 같은 과정을 한 번 수행하게 되면 리스트의 첫 번째 원소는 정렬이 된 상태가 되는 것이다.

 

 

이 과정을 마찬가지로 두 번째, 세 번째 원소에도 반복하여 수행하다 보면 결국 최종적으로 정렬된 리스트를 얻을 수 있게 된다.

 

 

 

특징

▶ 시간 복잡도는 O(N^2)이다. 가장 작은 원소를 탐색하는데 (N - 1), (N - 2), ... , 1번의 비교가 필요하기 때문에 정렬이 되어 있는 상태 이어도 O(N^2)의 시간 복잡도를 갖게 된다.

▶ 공간 복잡도는 O(1) 이다. 추가적인 삽입, 삭제 없이 위치를 바꿀 원소를 선택 후 위치만을 변경해주기 때문

▶ Unstable Sort이다. Unstable Sort란 동일한 값이 있을 경우 정렬 후 그 값들끼리 순서가 유지되지 않는 정렬이다. 위 예시를 봐도 알 수 있듯이 처음에 앞쪽에 위치하던 14가 정렬을 하는 과정에서 뒤쪽 14보다 뒤쪽으로 이동하게 되었고, 최종적으로 정렬은 뒤쪽에 있던 14가 앞쪽에 위치하게 되었다.

하지만 구현 방식을 다르게 하여 stable sort가 되게 할 수도 있다.

▶ 시간 복잡도를 보면 O(N^2)로 비효율적이지만 단순히 비교와 교체하는 동작만 구현하면 되므로 거품 정렬(Bubble Sort)과 마찬가지로 간단하게 구현이 가능하다.

단, 거품 정렬은 원소가 해당 위치로 이동하기 위해 그 거리 차이만큼 교환 작업을 수행해주어야 하지만 선택 정렬과 같은 경우 한 번씩만 교환을 수행하기 때문에 효율성은 같지만 훨씬 더 빠르다.

 

 

 

 

2. 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <iostream>
using namespace std;

void print(vector<int> v, string s);
void selection_sort(vector<int> v);
void selection_sort_reverse(vector<int> v);

int main() {
    vector<int> v = { 1, 7, 4, 3, 2, 9, 4 };
    selection_sort(v);
    selection_sort_reverse(v);

    return 0;
}


void print(vector<int> v, string s) {
    cout << s << " : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}

void selection_sort(vector<int> v) {
    int size = v.size();
    for (int i = 0; i < size - 1; i++) {
        int index = i;
        for (int j = i + 1; j < size; j++) {
            if (v[j] < v[index]) {
                index = j;
            }
        }
        int temp = v[i];
        v[i] = v[index];
        v[index] = temp;
    }
    print(v, "Selection Sort");
}

void selection_sort_reverse(vector<int> v) {
    int size = v.size();
    for (int i = 0; i < size - 1; i++) {
        int index = i;
        for (int j = i + 1; j < size; j++) {
            if (v[j] > v[index]) {
                index = j;
            }
        }
        int temp = v[i];
        v[i] = v[index];
        v[index] = temp;
    }
    print(v, "Selection Sort Reverse");
}

 

결과

 

● print / selction_sort / selection_sort_reverse 이 3개의 함수를 정의하였으며 각 함수명에서 기능을 유추할 수 있듯이 출력과 오름차순 선택 정렬, 내림차순 선택 정렬 기능을 하는 함수들이다.

 

 

 

● selction_sort 

 

1. index는 오름차순 정렬이기 때문에 최솟값의 위치를 의미하며, 임시로 현재 위치(i)를 index의 저장. 

 

2. i+1번 때부터 반복하여 index의 위치한 값과 비교하여, 더욱 적은 값을 가질 경우 해당 위치를 index의 저장하여야 한다.

 

3. 이 과정을 i+1 ~ size만큼 수행하면 가장 적은 값의 위치 값이 index의 저장되게 되고 i번 째 값과 교환해줌으로써 i번 째는 정렬된 상태가 된다.

 

 

 

● selection_sort_reverse 

 

위 오름차순 선택 정렬과 반대로 내림차순 선택 정렬을 수행하는 함수이다.

 

동작 방식은 동일하며 내림차순이기 때문에 최솟값 대신 최댓값의 위치를 선택하여 교환해줌으로써 내림차순으로 정렬이 되게 된다.