자료구조 :: 선택정렬 Selection sort (c/c++ 구현)

선택정렬 (Selection Sort)

 

가장 작은 값을 맨앞으로 보내자

 

정렬 알고리즘 중에서도 비효율적인 방법중 하나라고 할 수는 있지만,

간단하게 구현할 수 있는 알고리즘 중 하나다.

 

#include <stdio.h>
int main(void){
    int array[10] = {1, 9, 4, 10, 6, 2, 5, 3, 7, 8};
    int i, j, min, index, temp;
    
    for(i=0; i<10; i++){
        min = 9999;
        for(j=i; j<10; j++){
            if(min > array[j]){
                min = array[j];
                index = j;
            }
        }
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
    
    for(i=0; i<10; i++){
        printf("%d ", array[i]);
    }
    return 0;
}
​

 

 

위의경우 연산하는 횟수를 계산해본다면

 

10 + 9 + 8 + 7 + 6 + ... + 1 

=> 10 * (10 + 1) / 2

 

따라서,

선택정렬의 시간복잡도는 O(N^2)

N^2은 데이터의 개수가 늘어날수록 급격하게 연산량이 많아진다.

시간복잡도만 보더라도 선택정렬은 시간적인 면에서 비효율적이라는것을 알 수 있다.

 

관련 글

2018/04/29 - [Algorithm/백준 온라인 저지] - 백준/2750번 :: 수 정렬하기

2018/04/28 - [Algorithm] - 자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)