프로그래밍 불여일타!!의 프로젝트의 일환으로, 퇴근후 배깔고 하는 알고리즘 공부를 시작!!
그 결과물로 간단 간단한 알고리즘을 작성하고, 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 ] );
}
}
