선택정렬 (Selection sort)

▷ 선택정렬(Selection sort)

선택정렬은 가장 작은 값을 선택하여 그 값을 나열하는 과정을 반복하는 간단한 정렬 알고리즘이다.

배열에 존재하는 값중 가장 작은 값을 찾아서 첫 번째에 위치하는 값과 교환한다.

다음은 첫 번째를 제외한 나머지 값들 중 가장 작은 값을 찾아서 두 번째 위치하는 값과 교환한다.

이렇게 모든 배열이 정렬될 때 까지 게속한다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

▷ 정렬방법.

1. 처음 시작 시 가장 작은 값이 어떤 위치에 있는지 모르기 때문에 첫 번째 위치에 있는 값을 가장 작은 값으로 설정한다.

2. 값의 위치를 하나씩 옮기면서 가장 작은 값으로 설정했던 값과 비교한다.

3. 처음 설정했던 값보다 작은 값이 나오면 그 값을 가장 작은 값으로 설정하고 모든 값의 비교가 끝날때 까지 비교를 게속한다.

4. 모든 비교가 끝났으면 가장 작은 값과 첫 번째 값을 교환한다.

5. 첫 번째 값을 제외하고 1~4번의 과정을 반복한다.

※ 유의사항. 

- Min : 제일 작은 값.

- Index : 값의 인덱스.

- 제일 작은 값이 어떤 값인지 모른다고 가정한다.

- 처음 시작 시 0번째 인덱스를 제일 작은 값이라고 설정한다.

시작 : 5, 7, 3, 4, 9, 1

1).

- Min : 5

- Index : 0

Index : 0 [1] 2 3 4 5

value : 5 [7] 3 4 9 1

2).

- Min : 3

- Index : 2

Index : 0 1 [2] 3 4 5

value : 5 7 [3] 4 9 1

값과 인덱스를 기억.

3).

- Min : 3

- Index : 2

Index : 0 1 2 [3] 4 5

value : 5 7 3 [4] 9 1

4).

- Min : 3

- Index : 2

Index : 0 1 2 3 [4] 5

value : 5 7 3 4 [9] 1

5).

- Min : 1

- Index : 5

Index : 0 1 2 3 4 [5]

value : 5 7 3 4 9 [1]

값과 인덱스를 기억.

끝.

교환.

Index : [0] 1 2 3 4 [5]

value : [5] 7 3 4 9 [1]

첫 번째 값 : 5

끝의 값 : 1

두 개의 값의 자리를 교환한다.

교환완료.

Index : [0] 1 2 3 4 [5]

value : [1] 7 3 4 9 [5]

위의 과정을 모든 값들이 정렬될때 까지 반복한다.

Code

#include <iostream>
using namespace std;
 
#define MAX            6
 
void SelectSort(int *Number );
void main()
{
    int Number[MAX] = {5,7,3,4,9,1};
 
    SelectSort( Number );
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void SelectSort( int *Number )
{
    int Min;
    int Index;
 
    for(int i = 0; i < MAX; i++)
    {
        Min = Number[i];
        Index = i;
 
        for(int j = i + 1; j < MAX; j++)
        {
            if(Min > Number[j])
            {
                Min = Number[j];
                Index = j;
            }
        }
 
        int Temp = Number[Index];
        Number[Index] = Number[i];
        Number[i] = Temp;
    }
}

결과