[ 알고리즘 / 정렬 ] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)이란?

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을 지 선택하는 알고리즘이다.

선택 정렬 vs 삽입 정렬

선택 정렬은 배열에서 해당 자리를 선택하고 그자리에 오는 값을 찾는 것이라고 생각하면 편하다.

 

 Process 

① 주어진 배열 중에 최소값을 찾는다.

② 그 값을 맨 앞에 위치한 값과 교체한다.

③ 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 Code 

void SelectionSort(int DataSet[], int Lenght)
{
    for(int i = 0; i < Lenght; i++)
    {
        int MinIdx = i;
        for(int j = i; j < Lenght; j++)
        {
            if(DataSet[i] > DataSet[j])
            {
                MinIdx = j;
            }
        }
        int Temp = DataSet[MinIdx];
        DataSet[MinIdx] = DataSet[i];
        DataSet[i] = Temp;
    }
}

 시간복잡도 

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n (n-1) / 2 이므로  O(n^2)이다.

정렬이 되어 있던, 안되어 있던 비교하기 때문에 최선, 최악, 평균의 시간복잡도가 모두 동일하다.

 공간복잡도 

주어진 배열 안에서 교환하기 때문에, O(n)이다.

 장점 

- 구현이 간단하고 소스가 직관적이다. 알고리즘이 단순하다.

- 정렬하고자 하는 배열 안에서 교환하기 때문에, 다른 메모리 공간을 필요로 하지 않는다 => 제자리 정렬(in-place sorting)

- 1회전 당 비교는 계속 하지만 교환은 1회만 한다. (거품 정렬보단 빠르다.)

 단점 

- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.

- 불안정 정렬이다.

 

 정렬 알고리즘 시간 복잡도 비교