[알고리즘] 선택정렬 (Selection Sort)

선택정렬의 개념

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

선택정렬의 장단점

장점

• 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
• 자료 이동 횟수가 미리 결정된다.
• 비교횟수는 많지만 실제로 교환하는 횟수가 적기때문에 효율적이다.

단점

• 안정성을 만족하지 않는다.
• 값이 같은 숫자가 있는 경우에 상대적인 위치가 변경될 수 있다.

시간복잡도

데이터의 개수가 n개라고 했을 때
첫 번째 회전에서의 비교에서 첫번째 값 ~ n번째 값까지 비교하므로 n-1번
두 번째 회전에서의 비교횟수 두번째 값 ~ n번째 값까지 비교하므로 n-2번
...
$(n-1) + (n-2) + .... + 2 + 1 → n(n-1)/2$

즉 주어진 n개의 배열을 정렬하는데 필요한 시간복잡도는 $O(n²)$이다.
최선, 평균, 최악의 경우 모두 동일한 시간복잡도를 갖는다.

구현

#include <iostream>
#include <array>

using namespace std;

int main(){
    int temp;
    int index;
    int min;
    array<int, 8> arr = {2, 4, 1, 5, 3, 7, 6, 10};
    for(int i = 0; i < arr.size(); i++){
        min = arr[i];
        index = i;
        for(int j = i; j < arr.size()-1; j++){
            if(min > arr[j+1]){
                min = arr[j+1];
                index = j+1;
            }
        }
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    for(int i = 0; i<arr.size(); i++){
        cout << arr[i] << endl;
    }
}