[자료구조/Sorting] Selection Sort

 

Selection Sort

가장 작은 원소를 선택해서 교환하는 방식이다.

 

방법

아래의 방식을 첫번째 원소(i=0) 부터 마지막 원소-1(i=N-1) 까지 반복한다.

• 가장 작은 요소를 찾기 위해 배열을 검색
• 가장 작은 요소와 현재 배열의 원소를 교체

[C언어 코드]

void selectionsort (int array[], int len) {

    for (int i=0; i<len-1; i++) {

        int min_idx = i;

        for (int j=i+1; j<len; j++) {
            if (array[min_idx] > array[j])
                min_idx = j;
        }

        if (i!=min_idx) {
            int tmp = array[i];
            array[i] = array[min_idx];
            array[min_idx] = tmp;
        }
    }
}

과정

위와 같은 과정을 반복하여 Sorting 한다. 

시간복잡도

순서	복잡도
i=0	n-1
i=1	n-2
i=2	n-3
...	...
i=n-1	1

(n-1) + (n-2) + (n-3) + ... + 1 = n^2 = O(n^2)