선택 정렬이란 말이죠

선택 정렬(Selection Sorting)

삽입 정렬의 많은 데이터 이동량을 보완해 줄 정렬 알고리즘이다.

한 번에 하나의 자료를 선택해 해당 위치에 배정하는 정렬 방식을 사용한다.

리스트를 사용하면 포인터에 의해 데이터 이동을 없앨 수 있다.

 

선택 정렬 또한 카드게임에 비유해 설명해 보자

 

게임에 필요한 카드가 모두 손에 있는 상황에서, 카드를 크기 순으로 정렬하려 한다.

그 카드를 전부 살펴보고 가장 큰 값을 가장 오른쪽에 배치한다.

이후 그 다음 큰 값을 그 다음 오른쪽에 배치한다.

이 과정을 모든 카드가 정렬될 때까지 수행한다. (반대의 경우는 작은 값부터 왼 쪽에 정렬한다)

 

즉 선택 정렬의 수행 과정은 데이터 A[i], ..., A[n] 중 가장 작은 키 값을 갖는 데이터를 선택해 A[i]과 교환한다.

이런 단계를 계속하면 최종적으로 정렬된 리스트를 얻을 수 있다.

이 방법에선 최소(최대)의 데이터를 반복적으로 선택하므로 선택 정렬이라는 이름이 부여되었다.

1. 최대값(최소값) 찾아
2. 찾은 데이터와 맨 뒤(앞)에 데이터와 바꿈
3. 최대값(최소값) 찾아
4. 찾은 데이터와 맨 뒤(앞)에서 두 번째 데이터와 바꿈
...
n. 데이터 정렬 완료

 

 

작성

다음은 입력 데이터 크기가 n인 경우에 선택 정렬 알고리즘을 구현하였다.

1부터 n-1까지의 모든 i에 대하여 A[i], ..., A[n] 중의 최소 데이터와 A[i]를 교환한다

void selction_sort()
{
	int i, j, min;
    int temp;
    
    for (int i = 0; i < SIZE; i++)
    {
    	// 1. 최소값 찾기
        min = i;
        
        for (int j = i+1; j < SIZE; j++)
        {
        	if (L[j] < L[min]) min = j;
        }
        
        // 2. L[i], L[min] 교환
        temp = L[min];
        L[min] = L[i];
        L[i] = temp;
    }
}

 

인덱스 i가 입력 데이터를 따라 왼쪽에서 오른쪽으로 이동할 때, 인덱스 i의 왼쪽에 위치한 데이터들은 완전히 정렬된 상태가 된다.

 

 

특징

한 번 선택되어 이동한 자료는 재이동 없음 (삽입 정렬의 단점 보완)

수행 시간(On^2): 최상/최악/평균 모두 동일

비교 횟수
입력 데이터에서 최소값을 찾기 위해 (n-1)번 원소 값을 비교하게 된다.
따라서 총 비교 횟수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2이며, 비교의 수행 시간은 O(n^2)이 된다.