[알고리즘] 선택 정렬 알고리즘

안녕하세요.

오늘은 선택 정렬 알고리즘에 대해 알아보도록 하겠습니다.

 

선택 정렬 알고리즘

배열등 리스트에서 배열 위치에 맞게 오름/내림 정렬하는 알고리즘

 

구현 방법

오름차순 기준(제일 작은 값이 앞으로, 제일 큰 값이 뒤로 정렬)으로 설명하면,
첫 번째 데이터를 전체 데이터와 비교하여, 첫 번째 데이터와 제일 작은 값을 스왑 합니다.
다음 두 번째 데이터와 첫 번째를 제외한 전체 데이터와 비교하여 두 번째 데이터와 2번째로 작은 값을 스왑 합니다.
이것을 반복합니다.

예제

배열 arrData에 100, 20, 10, 12, 5 값이 있고, 최소값이 저장된 인덱스를 저장하기 위한 변수가 nIndex라면 다음과 같이 정렬됩니다.
nIndex의 초기값은 첫 번째 인덱스인 0입니다.

arrData[nIndex]의 값 100을 두 번째 값 20과 비교했을 때, 20이 더 작기 때문에 1을 nIndex에 저장합니다.
arrData[nIndex]의 값 20을 세 번째 값 10과 비교했을 때, 10이 더 작기 때문에 2를 nIndex에 저장합니다.
arrData[nIndex]의 값 10을 네 번째 값 12과 비교했을 때, 12이 더 크기 때문에 넘깁니다.
arrData[nIndex]의 값 10을 다섯 번째 값 5과 비교했을 때, 5가 더 작기 때문에 4를 nIndex에 저장합니다.
그 후 arrData[0]과 arrData[nIndex(=4)]를 스왑 합니다.(5, 20, 10, 12, 100)

다음으로 nIndex에 1을 넣고 비교를 합니다.
arrData[nIndex]의 값 20을 세 번째 값 10과 비교했을 때, 10이 더 작기 때문에 2를 nIndex에 저장합니다.
arrData[nIndex]의 값 10을 네 번째 값 12과 비교했을 때, 12이 더 크기 때문에 넘깁니다.
arrData[nIndex]의 값 10을 다섯 번째 값 100과 비교했을 때, 100이 더 크기 때문에 넘깁니다.
그 후 arrData[1]과 arrData[nIndex(=2)]를 스왑 합니다.(5, 10, 20, 12, 100)

다음으로 nIndex에 2를 넣고 비교를 합니다.
arrData[nIndex]의 값 20을 네 번째 값 12과 비교했을 때, 12이 더 작기 때문에 3을 nIndex에 저장합니다.
arrData[nIndex]의 값 12를 다섯 번째 값 100과 비교했을 때, 100이 더 크기 때문에 넘깁니다.
그 후 arrData[2]과 arrData[nIndex(=3)]를 스왑 합니다.(5, 10, 12, 20, 100)

다음으로 nIndex에 3을 넣고 비교를 합니다.
arrData[nIndex]의 값 20을 다섯 번째 값 100과 비교했을 때, 100이 더 크기 때문에 넘깁니다.
그 후 arrData[3]과 arrData[nIndex(=3)]를 스왑 하는 건 의미가 없으므로 최종 정렬이 됩니다.

 

코드

#include <iostream>
using namespace std;
 
void main()
{
    int arrData[5] = { 100, 20, 10, 12, 5 };
    int nTemp;
    int nIndex;
    int nSize = sizeof(arrData) / sizeof(int);
 
    cout << "before : ";
    for( int i = 0; i < 5; i++ )
        cout << arrData[i] << " ";
    cout << endl;
 
    for( int i = 0; i < nSize; i++ )
    {
        nIndex = i;
        for( int j = i; j < nSize; j++ )
        {
            if( arrData[nIndex] > arrData[j] )
            {
                nIndex = j;
            }
        }
 
        nTemp = arrData[i];
        arrData[i] = arrData[nIndex];
        arrData[nIndex] = nTemp;
        for( int k = 0; k < 5; k++ )
            cout << arrData[k] << " ";
        cout << endl;
    }
    cout << "after : ";
    for( int i = 0; i < 5; i++ )
        cout << arrData[i] << " ";
    cout << endl;
}