선택 정렬

선택 정렬(Selection Sort)은 매우 간단한 알고리즘이다. 

가장 작은 숫자의 index를 선택하고 이를 배열의 맨 처음 값과 비교해서 자리를 바꾸는 것이다.

ADL은 다음과 같다.

selectionSort(a[],n)
	for (i <- 1; i<n; i<- i+1) do {
    	minIndex <- i;
        for (j <- i+1; j<=n; j <- j+1) do
        	if (a[j] < a[minIndex]) then minIndex <- j;
        a[i]와 a[minIndex] 교환;
    }
end selectionSort()

간단한 예시로 [3,2,5,1,4]에 대해 선택 정렬을 해보겠다.

selection sort 예시

여기서 빨간색은 minIndex를 가리키는 것이고 파란색은 바꿀 값(처음부터 순차적으로)을 표시한 것이다.

서로 교환이 되면서 정렬이 이뤄지는 것이다.

이는 N개의 원소 각각에 대해 N-1 번 비교해야하기 때문에 \( \frac{N(N-1)}{2} \)가 되어 시간복잡도는 \( O(N^{2}) \)가 된다.

파이썬 코드는 다음과 같다.

def selectionSort(a,n):
    for i in range(1,n):
        minIndex = i
        for j in range(i+1,n+1):
            if a[minIndex] > a[j]:
                minIndex = j
        a[minIndex],a[i] = a[i],a[minIndex]
    return a

a = [-1,3,2,5,1,4]
print(selectionSort(a,len(a)-1))

여기서 n은 전체 길이에서 1을 뺀 값이고 -1이라는 null 값을 앞에 삽입하게 된다.