선택 정렬

선택 정렬은 주어진 원소 중에서 가장 작은 키값을 갖는 원소를 선택하여 차례대로 나열하는 정렬 방식이다.

arr [] = { 30, 50, 20, 10, 40 }의 배열로 선택 정렬을 이용하여 정렬해보자.

초기의 배열 상태

① 배열의 왼쪽에서 오른쪽으로 최솟값을 찾아나간다. 먼저 첫 번째 원소인 30을 최솟값으로 놓고 다음 원소 50과 비교한다. 30이 50보다 작으므로 최솟값은 여전히 30이다. 최소값인 30과 그 다음 원소인 20과 비교를 해보면 20이 30보다 작으므로 최소값이 20으로 바뀌게 된다. 최솟값인 20과 다음 원소 10을 비교하면 10은 20보다 작으므로 최소값이 10으로 바뀌게 된다. 오른쪽 끝까지 비교를 하면서 최소값을 찾은 후에는 첫 번째 원소와 최소값으로 찾은 네 번째 원소인 10과 교환을 한다.

첫 번째 원소에서부터 오른쪽으로 최소값을 검색 후 교환

1회전 배열 상태

② 다시 배열의 왼쪽에서부터 오른쪽으로 최소값을 찾아나간다. 첫 번째 원소는 검색이 끝난 원소이므로 두 번째 원소인 50부터 시작한다. 두 번째 원소인 50을 최소값으로 놓고 다음 원소 20과 비교 후 마지막까지 최솟값을 탐색하였을 때 최소값은 20이 된다.

 

두 번째 원소에서부터 오른쪽으로 최소값을 검색 후 교환

2회전 배열 상태

③ 위의 과정을 계속 진행하다 보면 최종적으로 아래와 같은 정렬된 결과를 얻을 수 있다.

선택 정렬 결과

 

이제 코드로 선택 정렬을 구현해보자.

 

#include <iostream>
 
using namespace std;
 
// 원소 개수
#define MAX_LENGTH 5
 
int main()
{
    // 정렬할 배열 선언
    int arr[MAX_LENGTH] = { 30, 50, 20, 10, 40 };
 
    // 최소값을 담아둘 변수 선언
    int min = 0;
 
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        // 최소값 설정
        min = i;
 
        // 최소값으로 설정한 원소 다음 위치 부터 마지막 원소까지 순회
        for (int j = i + 1; j < MAX_LENGTH; ++j)
        {
            // 최소값보다 작은 원소를 찾았을 경우
            if (arr[min] > arr[j])
            {
                // 최소값 저장
                min = j;
            }
        }
 
        // 원소 교환
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
 
    // 출력 결과 확인
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        cout << arr[i] << endl;
    }
}