Selection Sort (선택 정렬)

1. 개념

선택정렬이란 배열에서 먼저 원소를 넣을 위치를 정해놓고, 그 위치에 어떤 원소를 넣을지 하나하나 탐색하면서 정렬하는 알고리즘이다. 예를 들어 아래와 같은 배열이 있으면

8 4 6 5 3 2 1 9 7 먼저 첫번째 인덱스부터 위치를 선택하여 가장 작은 값인 1을 찾는다. 이후 그 인덱스의 숫자와 우리가 넣어줄 숫자의 위치를 바꾼다. 이를 차례대로 진행하면 먼저 1과 8을 바꿔준다. 1 4 6 5 3 2 8 9 7 이후 다시 4와 2를 바꿔준다. 1 2 6 5 3 4 8 9 7 같은 방법으로 순차적으로 진행하면 1 2 3 5 6 4 8 9 7 ........ 1 2 3 4 5 6 7 8 9 이를 c코드로 하면 아래와 같다.

2. 코드

#include <iostream>
using namespace std;

int main()
{
    int a[100], n, idx, i, j, tmp; 
    // a는 배열, n은 입력받을 index의 개수
    scanf("%d",&n);
    for(i =0; i<n; i++){
        scanf("%d",&a[i]);
    }
    for(i=0; i<n-1; i++){
        idx = i;  //먼저 바꿔줄 위치를 지정
        for(j= i+1; j<n; j++){
            if(a[idx]>a[j]) idx = j; //이후 가장 작은 값의 idx를 찾기
        }
        // min값의 index를 발견하면 이를 swap
        tmp = a[i];
        a[i] = a[idx];
        a[idx] = tmp;
    }
    for(i=0; i<n; i++){
        printf("%d ",a[i]);
    }
    
    return 0;
}

시간복잡도

데이터의 갯수가 n이라고 하면, 총 루프의 횟수는 n(n-1)/2 이므로 시간복잡도는 O(n^2) 이다.

장점과 단점

장점

• 단순한 알고리즘
• 정렬을 위한 비교 횟수는 많지만 실질적으로 swap을 하는 횟수는 적기 때문에 교환이 적어야하는 자료 구조에서는 효율적으로 사용 가능

단점

• 시간복잡도가 (O^2)으로 비 효율 적이다.
• 불안정 정렬이다. 만약에 중복된 숫자 2213(이해를 위해 bBac) 이라고 있을경우, 선택정렬을 하면 2213(aBbc)가 된다. 이처럼 같은 데이터지만 순서가 유지되지 않을 수도 있기때문에 불안정 정렬이다.