2016. 12. 8. 17:10


안녕하세요. 게임 개발자 놀이터입니다.


이번 포스팅에선 선택 정렬에 대해서 정리해보려고해요.


벌써 버블, 삽입 2개를 하고 선택정렬할 차례네요..


간단한건 이제 끝나가는군요.



선택 정렬


선택 정렬은 크게 3가지 방법으로 정렬을 합니다.


1. 주어진 배열에서 최솟값을 찾는다.

2. 그 값을 배열 맨앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.



정렬 과정


우선 랜덤하게 숫자를 배열해보겠습니다.


9 5 4 3 8 1 7


우선 정렬이 안된 배열 {9 5 4 3 8 1 7} 에서 최 하위 값을 찾습니다.


1 이군요. 찾은 값을 젤 처음 값과 교체합니다.


9 5 4 3 8 1 7 => 1 5 4 3 8 9 7


이렇게 한번의 루프가 끝났습니다.


두번째는 맨 처음 값 그러니까 교체가 된 1을 제외한 배열을 정렬합니다.


1 { 5 4 3 8 9 7 } 에서 최 하위 값을 찾습니다. 3 이군요. 1을 제외한 배열 처음과 교체합니다.


1 3 4 5 8 9 7 이 되겠군요.


이런식으로 마지막까지 진행하면 정렬이 됩니다.


밑의 그림을 참고해주세요.


(출처 : 위키백과 선택정렬)



예제 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SelectionSort(int arrays[], int length) 
{
    for(int i=0; i<length; ++i)
    {
        int Minindex = i;
        for(int j= i+1; j<length; ++j)
        {
            if(arrays[j] < arrays[Minindex])
                Minindex = j;
        }
 
        int swap = arrays[i];
        arrays[i] = arrays[Minindex];
        arrays[Minindex] = swap;
    }
}
cs


간단하게 구현했습니다.



알고리즘 분석


선택 정렬은 최소값을 구하기 위해 전부 비교를 해야합니다. 따라서


(n-1) + (n-2) + ..... + 2 + 1 = n(n-1)/2 가 됩니다.


빅 오 표기법으로 시간 복잡도는 O(N²)가 되겠습니다.




그림 예시 자료



(출처:  위키백과 선택정렬 )


동영상 예시 자료

( 출처 : Youyube )




감사합니다.

Posted by 시리시안