처음으로 작성하는 알고리즘 글이네요. 학교에서 배우는 알고리즘을 꼭 기록으로 남겨야 겠다고 생각했었는데 드디어 기회가 왔습니다.
첫번째로 선택정렬을 살펴보도록 하겠습니다. 너무 쉬워서 볼 필요가 없을것도 같지만 아는게 힘이니깐 하나하나 적어볼께요.
선택정렬은 원소의 수(N)만큼 순환을 돌면서 매 순환마다 가장 작은 수를 찾아 가장 앞으로 보내는 정렬 방법입니다.
왼쪽은 순환을 도는 모습을 그려보았습니다. 그림을 보고 다음과 같은 내용을 알 수 있습니다.
1. 정렬할 원소가 5개가 있다.
▷ 5번의 반복 순환을 해야 한다.
2. 매 순환마다 비교 대상자가 줄어든다.
▷ 매 순환마다 N - 1 번의 비교를 하게 된다.
예)
N = 5(i = 0) : 0번째 원소와 나머지 4개를 비교
N = 3(i = 2) : 2번째 원소와 나머지 2개를 비교
3. 매 순환당 레코드 교환은 한번 일어난다.
▷ 작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합
4. 실행시간은 입력자료의 순서에 상관없다.
▷ 입력자료의 순서에 민감하지 않다.
5. 추가적인 기억장소를 요구하지 않는다.
▷ 제자리 정렬이다.
6. 교환에 의해 동일한 키(값)를 가지는 레코드의 상대적인 위치가 유지되지 않을 수 있다.
▷ 불안정적인 알고리즘이다.
선택 정렬 알고리즘은 N개의 원소 각각에 대해 N - 1 번의 비교를 해야 하므로 전체 비교횟수는
(N - 1) + (N - 2) + (N - 3) + ... + 3 + 2 + 1 = N(N - 1) / 2
가 되어 시간 복잡도는 O(N²)가 됩니다.
void SelectionSort(int nList[])
{
int nMinimum, nFind;for(int nIndex = 0 ; nIndex < MAX_LENGTH ; nIndex++)
{
nMinimum = nIndex;
nFind = nIndex;
for(int nCompare = nIndex + 1 ; nCompare < MAX_LENGTH ; nCompare++)
{
if(nList[nCompare] < nList[nFind])
{
nFind = nCompare;
}
}
Swap(nList, nFind , nMinimum);
}
}