2. 선택 정렬(Selection Sort)

ㆍ비효율적인 정렬 알고리즘

 

ㆍ예를 들어 1 10 5 8 7 6 4 3 2 9 가 있을 때 이를 선택 정렬로 정렬하는 경우

1) 처음부터 끝까지 10개를 살펴본 후 -> 가장 작은 걸 앞에 둠

2) 또 두번째부터 끝까지 9개를 살펴본 후 -> 가장 작은 숫자(2를) 가장 앞(두번째자리)의 숫자와 위치를 바꿈

 

즉 "가장 작은 걸 선택해서 가장 앞으로 보낸다"

 

#include <stdio.h>

int main(void) {
    int i, j, min, index, temp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for (i=0; i<10; i++) {
        min = 9999;		//모든 원소보다 큰 숫자인 9999 넣음.
        for(j=i; j<10; j++) {
            if(min>array[j]) {		//현재 탐색하는 원소가 최소값보다 작으면
                min = array[j];		//최소값을 현재 탐색하고 있는 원소로 바꿈
                index = j;	//index에 해당 위치값을 넣어줌
            }
        }
        // 가장 앞에 있는 숫자와 최소값의 위치 바꾸기
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
    for(i=0; i<10; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

 

 

출력 결과

 

 

선택정렬의 시간복잡도

위의 경우에서 10+9+..._2+1 를 실행한다. 이는 등차수열로 10 x (10 + 1) / 2이 계산된다.

즉 N개의 항목일 때 N x (N+1) / 2 번 실행된다.

 

따라서 수행시간은 O(n x n)이다. 비효율적이다.

 

참고 글 : https://blog.naver.com/ndb796/221226800661