선택 정렬

선택 정렬

배열을 전체 스캔을 통해서 가장 우선순위가 되는 원소를 맨 앞으로 이동시킨다. 즉, 버블 처럼 순간순간 비교하여 바꾸는 것이 아니라 배열 전체 스캔 후 1번. 이것을 정렬이 끝날 때 까지 반복한다

. 버블 정렬보다는 성능이 좋지만 O(N^2) 이다. 좋지 않음

 

void SelectionSort(vector<int>& v)
{
    const int n = (int)v.size();

    for (int i = 0; i < n - 1; i++)
    {
        int bestI = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (v[j] < v[bestI])
                bestI = j;
        }

        // swap
        int temp = v[i];
        v[i] = v[bestI];
        v[bestI] = temp;
    }
}