선택 정렬 (Selection Sort)

최댓값 혹은 최솟값을 하나씩 찾아서 한쪽으로 몰아넣는 방식.

예를들어 오름차순 정렬이라고 한다면,

1. 배열 전체 순회하면서 최댓값을 찾음
2. 맨 오른쪽에 배치.
3. 정렬한 숫자 빼고 나머지 또 다 순회해서 그 다음으로 큰 값을 찾음.
4. 정렬 안된 숫자 중 가장 오른쪽 배치
5. 반복.

int min_index;
for (int i = 0; i < size - 1; i++)
{
    min_index = i;
    for (int j = i + 1; j < size; j++)
    {
        if (arr[j] < arr[min_index])
        {
            min_index = j;
        }
    }
    swap(arr[i], arr[min_index]);
}

Worst-case O(n^2) 성능

https://en.wikipedia.org/wiki/Selection_sort

Selection sort - Wikipedia