선택 정렬이란 ? 어떤한 숫자열에서 가장 작은것을 앞으로 보내는것
int array[10] = { 10,2,3,6,4,5,7,8,9,1 };
int index = 0;
int min = 0;
int temp = 0;
for (int i = 0; i < 10; i++) {
min = 99999;
for (int j = i; j < 10; j++) {
if (min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
다음의 시간복잡도는
10 + 9 + 8 + ... + 1
과 같은 등차수열로 확인할 수 있다 이는
10 (10 + 1) / 2 = 55 ->
N (N+1) / 2 일반적으로 컴퓨터에서는 N 의값이 굉장히 크다는 가정하에 간단하게 나누거다 더하는 연산은 무시한다 따라서 O(N * N) 이라고 표현할 수 있다. 이때 사용하는것이 빅 O 표기법 이다.