[알고리즘] Selection Sort

프로그래밍 불여일타!!의 프로젝트의 일환으로, 퇴근후 배깔고 하는 알고리즘 공부를 시작!!
그 결과물로 간단 간단한 알고리즘을 작성하고, Blog에 올리기로 했습니다.

오늘은 간단하게 Selection Sort를 만들어 보았습니다.

* 원리는 : 총 1...n개의 정렬 되지 않은 요소에서, 첫번째 놈을 가져다가 가장 작은 값을
              가진다라 가정 하고  나머지 n-1개와 비교를 하게 합니다. 그래서 그중 가장
              작은 녀석을 기억 하고 있다가, 1번째 자리와 바꿉니다. 그리고 index을 하나 더
              증가 해서 두번째 요소를 가지고  n-2 만큼 loop를 돌아서 다시 최소값을 찾고
              바꿔 줍니다. 이렇게 반복하면 정렬이 됩니다.( 사실 그림으로 보면 아무것도
              아닙니다. 그림은 귀찮아서 안그렸습니다.)

* 성능 :  O(N^2)

* 코드

void swap( int *a, int *b )
{
     int dump = *a;
     *a = *b;
     *b = dump;
}

void SelectionSort( int *_arrayBuffer, const unsigned int _arraySize )
{
     for( int i = 0; i < _arraySize; i++ )
     {
          int nMinIndex = i;
          for( int j = i + 1; j < _arraySize; j++ )
          {
               if( _arrayBuffer[j] < _arrayBuffer[nMinIndex] )
               {
                   nMinIndex = j;
               }
          }
          swap( _arrayBuffer[nMinIndex], _arrayBuffer[ i ] );
      }  
}