[Algorithm] 선택 정렬

가장 작은 것을 선택하여 제일 앞으로 보내는 정렬 방법

 

▶ 흐름은 다음과 같다.

1. 맨 앞에서부터 차례로 돌며 가장 작은 수 찾기
2. 가장 작은 수 <-> 맨 앞에 있는 수
3. 2번째 수부터 차례로 돌며 2번째로 작은 수 찾기
4. 2번째 수 <-> 2번째로 작은 수
5. 위의 과정을 n번째까지 반복

 

▶ C++ 코드

#include <stdio.h>

int main(){
    int i, j, min, index, temp;
    int array[10] = { 1, 10, 8, 7, 5, 4, 6, 3, 2, 9};

    for(i=0; i<10; i++){
        min = 9999; // 가장 작은 값 받아야 하기 때문에 모든 데이터보다 큰 수
        for(j=i; j<10; j++){
            if (array[j] < min) {
                min = array[j];
                index = j;
            }
        }
        // swap
        temp = array[i];
        array[i] = min; // 제일 작은 수 앞으로 보내기
        array[index] = temp;
    }

    for (i = 0; i < 10; i++) {
		printf("#%d %d\n", i, array[i]);
	}

	return 0;
}

출력 결과

---

▶ 시간복잡도

 

- 처음부터 끝까지 돌며 가장 작은 수 찾기 (n)

- 처음부터 끝까지 돌며 가장 작은 수와 교환해주기 (n)

 

앞선 예시를 보면,

10개 살펴보기 > 맨 앞 제외한 9개 살펴보기 > 2번째까지 제외한 8개 살펴보기 ... >> 10+9+...+1 = (10*11)/2

 

- n(n+1)/2

>> O(n^2)