[알고리즘] 선택 정렬 알고리즘

선택정렬

선택 정렬은 여러 개의 데이터가 무작위로 있을 때 전체 데이터에서 매번 가장 작은(또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용합니다. 선택 정렬의 종류는 2가지로 나눌 수 있습니다.

 

• 최소 선택 정렬(Min-selection sort): 매번 가장 작은 데이터를 선택하고 데이터 간의 배치를 변경하며 오름차순으로 정렬
• 최대 선택 정렬(Max-selection sort): 매번 가장 큰 데이터를 선택하고 데이터 간의 배치를 변경하며 내림차순으로 정렬

선택정렬은 어떻게 동작하는가?

최소 선택 정렬의 경우 구체적인 동작 과정은 다음과 같습니다.

 

1. 전체 데이터에서 가장 작은 데이터를 선택하고 맨 앞에 있는 데이터와 자리를 바꿉니다.

2. 그다음으로 작은 데이터를 선택하고 맨 앞에서 두 번째 데이터와 자리를 바꿉니다.

3. 위와 같은 방식으로 오름차순으로 정렬이 완료될 때까지 데이터를 선택하고 자리를 바꾸는 과정을 반복합니다.

 

 

IndexValue

0	모든 값 중에서 가장 작은 값
1	첫번째 값(Index=0)을 제외하고 남은 값 중에서 가장 작은 값
…	…
i	i번째 부터 n-1 번째까지 값 중 가장 작은 값
…	…
n-2	n-2번째와 n-1 번째까지 값 중 가장 작은 값
n-1	마지막에 남은 하나의 값 (비교 대상 없음)

즉, 크기 n의 배열이 주어졌을 때, index 0부터 n-1까지의 모든 index i에 대해서, i번째 부터 n-1 번째까지 값 중 가장 작은 값을 구해서 index i에 놓으면 정렬된 배열을 얻을 수가 있습니다. 모든 index에 대해서 그 index에 위치시킬 값을 “선택”하기 때문에 이 정렬 알고리즘을 “선택 정렬”또는 “Selection Sort”이라고 부릅니다.

실전 예제

아래와 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열을 위에서 설명한 선택 정렬 알고리즘을 이용하여 정렬을 해보겠습니다. i는 현재 index, m은 가장 작은 값이 있는 index를 가르킵니다.

 i
[3, 4, 5, 1, 2]
          m

우선 index 0에 놓을 값을 찾아야 합니다. 모든 숫자 중 가장 작은 숫자인 1을 index 3에서 찾았습니다. 1을 index 0에 위치시키기 위해서 위해서 원래 index 0에 있던 3과 1의 자리를 바꿉니다.

    i
[1, 4, 5, 3, 2]
             m

다음으로 index 1에 놓을 값을 찾아야 합니다. 1을 제외하고 남은 숫자 중에서 가장 작은 숫자인 2를 index 4에서 찾았습니다. 2를 index 1에 위치시키기 위해서 원래 index 1에 있던 4와 2의 자리를 바꿉니다.

       i
[1, 2, 5, 3, 4]
          m

다음으로 index 2에 놓을 값을 찾아야 합니다. 1, 2를 제외하고 남은 숫자 중에서 가장 작은 숫자인 3를 index 3에서 찾았습니다. 3를 index 2에 위치시키기 위해서 원래 index 2에 있던 5와 3의 자리를 바꿉니다.

          i
[1, 2, 3, 5, 4]
             m

다음으로 index 3에 놓을 값을 찾아야 합니다. 1, 2, 3를 제외하고 남은 숫자 중에서 가장 작은 숫자인 4를 index 4에서 찾았습니다. 4를 index 3에 위치시키기 위해서 원래 index 3에 있던 5와 4의 자리를 바꿉니다.

             i
[1, 2, 3, 4, 5]
             m

마지막으로 index 4에 놓을 값을 찾아야 합니다. 1, 2, 3, 4를 제외한 남은 숫자는 5 밖에 없으며 따라서 지동으로 5가 가장 작은 숫자가 됩니다.

복잡도 분석

• 선택 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
• 시간 복잡도는 우선 루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 하나의 루프에서는 현재 인덱스의 값과 다른 인덱스의 값들과 비교하여 최소값을 찾은 후 현재 인덱스에 있는 값과 상호 자리 교대를(swap)해야 해야하기 때문에 O(N)을 시간이 필요하게 됩니다. 따라서 선택 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.

알고리즘 특징

• 선택 정렬은 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 됩니다. 따라서, 뒤에 있는 index로 갈수록 비교 범위가 하나씩 점점 줄어드는 특성을 가지고 있습니다. (index 0에서는 0부터 n-1까지 비교해야 되지만, index n-1에서는 남은 숫자가 하나 밖어서 비교가 필요 없음)
• 입력 배열이 이미 정렬되어 있건 말건 관계없이 동일한 연산량을 가지고 있기 때문에 최적화 여자가 적어서 다른 O(N^2) 대비해도 성능이 떨어지는 편입니다.
• 이러한 성능 상의 한계 때문에 실전에서는 거의 보기 힘들지만, 가장 구현이 쉬운 정렬 알고리즘이라서, 알고리즘 수업 시간에는 한 번씩 꼭 접하게 되는 유명한 정렬 알고리즘입니다.

구현

두 개의 반복문이 필요합니다. 내부 반복문에서는 현재 index부터 마지막 index까지 최소값의 index를 찾아내고, 외부 반복문에서는 이 최소값의 index와 현재 index에 있는 값을 상호 교대(swap)합니다. 외부 반복문에서는 index i를 0에서 n-2(또는 n-1. 마지막 index에서는 남는 값이 하나 밖에 없기 때문에 대세에 지장 없음)까지 진행시키며, 내부 반복문에서 이미 정렬된 값들에서는 관심이 없기 때문에 index j를 i에서 n-1까지 진행시킵니다. 각 index에 대해서 최소값을 찾기 위해 대소 비교는 여러번 일어나나 상호 교대(swap)은 딱 한번만 알어납니다.

 

아래는 선택정렬의 ADL 코드입니다.

selectionSort(a[], n)
	for(i<-1;i<n;i<i+1) do { // 마지막 원소를 제외한 나머지 원소들이 올바른 위치에 있을 경우 마지막 원소는 제 자리에 있을 것임.
    	minIndex <- i; // i 루프를 돌면서 최솟값을 지정할 인덱스 값 순환
   	    for(j<-i+1;j<=n;j<-j+1) do 
    	  if (a[minIndex] > a[j]) then minIndex <- j;
         a[i]와 a[minIndex]를 교환;
    }
    end selectionSort()

아래는 선택정렬의 파이썬 코드입니다.

def slectionSort(a,n):
for i in range(1,n)
	minIndex = i
    for j in range(i+1, n+1):
    	if a[j] < a[minIndex]:
    	minIndex = j
     a[minIndex], a[i] = a[i], a[minIndex]

 

첫 번째 반복문에서 인덱스 값을 n-1로 설정한 이유는 

마지막 원소를 제외한 모든 원소들이 올바른 위치에 들어가게 될 경우 남는 a[n]은

자동적으로 가장 큰 값이 되기 때문에 제 위치에 있게 될 것입니다.

 

선택 정렬 알고리즘은 N개의 원소 각각에 대해 N-1번의 비교를 해야되기 때문에 전체 비교 횟수는 N(N-1)/2가 되어 

전체 시간 복잡도는 O(N^2)가 됩니다.

 

 

작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합합니다.

 

실행 시간은 입력 자료의 순서에 민감하지 않습니다.

 

제자리 정렬입니다.

 

교환에 의해 동일한 키를 가지는 레코드의 상대적인 위치가 유지되지 않을 수 있으므로 불안정적인 알고리즘입니다.