자료구조) 선택 정렬 (Selection Sort)

선택 정렬은 정렬되지 않은 데이터(리스트)에 대해 가장 작은 데이터를 찾아 가장 앞 데이터와 교체하는 과정을 반복해 가장 작은 데이터부터 가장 큰 데이터까지 순서대로 정렬하는 것이다.

선택 정렬은 아래와 같은 순서로 이루어진다.

1. 주어진 리스트 중에 제일 작은 값(최솟값)을 찾는다.
2. 그 값과 맨 앞에 위치한 값을 교체한다 (std::swap)
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

void SelectionSort(int* list, int size)
{
    int min_index = 0;
    for (int i = 0; i < size - 1; i++)
    {
        min_index = i;
        for (int j = i + 1; j < size; j++)
        {
            if (list[min_index] > list[j])
                min_index = j;
        }
        std::swap(list[i], list[min_index]);
    }
}

참조) Selection sort - Wikipedia