선택정렬(Selection Sort)란 무엇일까?

선택정렬

• 제자리 정렬 알고리즘중 하나이다.

• O(n2)만큼의 시간이 걸린다.

• 메모리가 제한적인 경우 사용시 성능 상의 이점이 있다.

선택정렬은 다음과 같은 순서로 이루어집니다.

1. 첫번째 인덱스에 들어갈 리스트중 최소값을 찾는다.
2. 찾은 최소값과 첫번째 인덱스 값을 교체한다.
3. 두번째 인덱스로 넘어간다.
4. 1~2방법을 반복하며 마지막인덱스까지 진행한다.

 

이해를 돕는 영상

 

[C++]

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
            	//최소값의 인덱스
                indexMin = j;
            }
        }
        //스왑(최소값과 현재값의 교체)
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}