[알고리즘 c++] 선택정렬

선택 정렬 알고리즘이라고 하면 가장 작은 수를 가져와 맨 앞으로 가져오고, 가져온 수의 자리에 맨 앞에 있던 숫자를 스와핑하는 방식으로 배열의 수만큼 반복하는 식으로 오름차순, 내림차순으로 정렬하는 알고리즘 방식입니다.

#include <stdio.h>

int main(void) {
  int i, j, min, index, temp;
  int array[10] = {10,1,5,8,7,6,4,3,2,9};
  for(i=0; i<10; i++){
     min = 9999;
     for(j=i; j< 10; j++){
     if(min > array[j]){
        min= array[j];
        index = j;
     }
     }
     temp = array[i];
     array[i] = array[index];
     array[index] = temp;
  }
  
  
  for(i = 0; i< 10;i++){
     printf("%d ", array[i]);
  }
  
  return 0;
}

위 예제처럼 길이가 10인 배열을 선택 정렬 알고리즘으로 정렬할 경우

등차수열로 표현하면 아래와 같이

10 + 9 + 8 + ... + 1
55번의 참조가 발생하는데

10 * (10 + 1) / 2

N * (N + 1) / 2

시간 복잡도를 판단하는 빅 오 표기법에서 +1이나 /2 같은 작은 수를 생략하기 때문에

O(N * N) 라는 공식이 나옵니다.

선택 정렬의 시간 복잡도는 O(N^2) 입니다.

즉 배열의 길이가 10000 이면 10000 * 10000 = 100000000번의 참조가 발생한다고 판단하는 것인데, 매우 비효율적인 알고리즘이라고 할 수 있습니다 ^^;

_빅 오 표기
: 알고리즘에서 시간의 복잡도를 표시하기 위하여 대문자 오(O)를 사용하여 나타내는 표기. O(n), O(2) 따위와 같이 표기한다.

참고 : https://ndb796.tistory.com/