[Algorithm] 선택 정렬(Selection Sort)

선택 정렬(Selection sort)

: 가장 작은 것을 선택해서 가장 앞으로 보내는 알고리즘

 

1	10	5	8	7	6	4	3	2	9
1	10	5	8	7	6	4	3	2	9
1	2	5	8	7	6	4	3	10	9
1	2	3	8	7	6	4	5	10	9
1	2	3	4	7	6	8	5	10	9
1	2	3	4	5	6	8	7	10	9
1	2	3	4	5	6	8	7	10	9
1	2	3	4	5	6	7	8	10	9
1	2	3	4	5	6	7	8	10	9
1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10

 

코드

#include <iostream>
using namespace std;

int main(void){
    // 선택 정렬: 가장 작은 것을 선택해서 가장 앞으로 보내자
    int i, j, min, idx, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        min = 9999;
        for(j=i;j<10;j++){
            if(min > array[j]){
                min = array[j];
                idx = j;
            }
        }
        tmp = array[i];
        array[i] = array[idx];
        array[idx] = tmp;
        cout << array[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

 

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 9) / 2

=> N * (N - 1) / 2

∴ O(N^2)