[C++] 선택정렬 (Selection Sort)

[선택정렬]

가장 작은 값을 선택해서 앞으로 보내준다

[문제]

  1,10,5,8,7,6,4,3,2,9 를 순서대로 정렬하세요

[풀이]

#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++) { //총10번을 반복

min = 9999; //항상 최소값을 선택해야하기때문에 일단 가장큰 값을 넣음

for (j = i; j < 10; j++) {

if (min > array[j]) { //배열중에 min보다 작다면

min = array[j]; //min에 넣어줌

index = j; //해당 위치값을 인덱스에 넣어줌

//여기까지 한번탐색했을때 가장작은값을 선택함

}

}

//스와핑 : 두개의 값의 자리를 바꿔준다

//위에서 선택한 가장작은값을 맨앞으로 보내줌

temp = array[i];

array[i] = array[index];

array[index] = temp;

}

for (i = 0; i < 10; i++) {

printf("%d", array[i]);

}

} 

[문제점]

첫번째 확인할때 10번 확인 1~10

두번째는 9번 확인 2~10

....

1 번 확인

등챠수열 -> n * (n+1) / 2  ->  o(n*n)  -> 10*(10+1)/2 =55

10개를 정렬하기 위해서 55번의  확인이 필요함