선택 정렬(selection sort)

이전에는 효율성이 O(N2)인 데이터 정렬 알고리즘인 버블 정렬(bubble sort)을 살펴보았다. 이번에는 선택 정렬(selection sort)라는 다른 정렬 알고리즘을 알아보고 버블 정렬과 효율성을 비교해 보겠다.

 

선택 정렬의 루프를 알아보자.

 

먼저 인덱스 0에 들어 있는 값을 확인하며 시작하여 최솟값으로 지정한 후, 다음 인덱스와 비교한 다음 최솟값을 결정한다.

loop1 min_Index = 0 (값 = 5) [5, 3, 2, 1, 4] 인덱스 0과 1의 비교 min_Index = 1 (값 = 3) [5, 3, 2, 1, 4] 인덱스 1과 2의 비교 min_Index = 3 (값 = 2) [5, 3, 2, 6, 4] 인덱스 2과 3의 비교 min_Index = 3 (값 = 2) [5, 3, 2, 6, 4] 인덱스 2과 4의 비교 min_Index = 3 (값 = 2) => [2, 5, 3, 6, 4]

 

첫번째 루프를 돌았을 때, 가장 작은 인덱스는 3이며 값은 2이다.

결과는 [2, 5, 3, 6, 4] 이다.

이제 0번 인덱스의 자리는 비교 할 필요가 없으므로 1번 인덱스부터 비교를 한다.

 

loop2 min_Index = 0 (값 = 5) [2, 5, 3, 6, 4] 인덱스 1과 2의 비교 min_Index = 2 (값 = 3) [2, 5, 3, 6, 4] 인덱스 2과 3의 비교 min_Index = 3 (값 = 2) [2, 5, 3, 6, 4] 인덱스 2과 3의 비교 min_Index = 3 (값 = 2) => [2, 3, 5, 6, 4]

이런식으로 한 루프마다 최솟값을 조회하여 지정 된 인덱스와 자리를 바꿔준다.

 

그래서 전체 루프를 돌아보면

 

loop3 => [2, 3, 4, 5, 6]

 

세번만에 정렬이 끝난 것을 알 수 있다.

 

선택 정렬을 파이썬 코드로 구현을 해보았다.

 

def selectionSort(array):
    
    for i in range(len(array)):
        smallIndex = i
        
        for j in range(i+1,len(array)):
            if(array[j] < array[smallIndex]):
                smallIndex = j
    
        if(smallIndex != i):
            temp = array[i]
            array[i] = array[smallIndex]
            array[smallIndex] = temp

    return array

 

코드를 하나씩 살펴보자.

 

for i in range(len(array)):
    smallIndex = i

 

변수 i를 사용하여 첫번째 루프에 들어갈 최솟값을 smallIndex 변수로 지정해준다.

 

for j in range(i+1,len(array)):
    if(array[j] < array[smallIndex]):
        smallIndex = j

 

j 변수에는 i보다 +1된 값이 되며 들어온 배열의 길이 만큼 순위하며 최솟값과 j 인덱스의 값과 비교하여 j인덱스가 최솟값 보다 작으면 j인덱스를 smallIndex로 바꿔준다.

 

if(smallIndex != i):
    array[i], array[smallIndex] = array[smallIndex], array[i]

이전에 루프에서 j값들과 smallIndex를 비교하였을때 애초에 smallIndex가 작아서 지정 된 처음 그대로의 i값이 들어 있을 수 있다. 그래서 smallIndex와 i를 비교하였을때 같지 않으면 교환이 일어난 것이므로 i번째 인덱스를 smallIndex로 바꿔준다.

 

return array

 

모든 루프가 끝난 후 배열을 반환한다.

 

선택 정렬의 효율성은 비교와 교환 두 종류의 단계를 포함한다.

만약 5개의 원소를 포함하는 배열이면 4 + 3 + 2 +1 = 10번의 비교

교환은 패스스루당 최대 1번이며, 최악의 시나리오에서는 빠짐없이 교환을 한 번 한다.

 

버블 정렬과 선택정렬을 비교해보자.

 

원소 개수(N)	버블 정렬의 최대 단계	선택 정렬의 최대보 단계
5	20	14(10번의 비교 + 4번의 교환)
10	90	199(180번의 비교 + 19번의 교환)
20	1560	819(780번의 비교 + 39번의 교환
80	6320	3239(3160번의 비교 + 79번의 교환)

 

표에서 비교한 바에 따르면 선택 정렬은 버블정렬보다 단계 수가 반정도 적다. 선택 정렬이 두배 더 빠르다.

실제로 선택 정렬의 효율은 O(N2 / 2) 이지만 빅오 표기법은 상수를 무시하기 때문에 효율성을 O(N2)로 표기한다.

 

두 알고리즘이 같은 카테고리에 속하더라도 서로 처리 속도가 다르다. 버블 정렬과 선택 정렬은 둘 다 O(N2)이지만 선택 정렬이 두배 빠르다. 빅 오에서 서로 다른 카테고리에 속하는 알고리즘을 대조할 때는 빅 오가 완벽한 것 같지만 같은 카테고리에 속한 알고리즘이면 어떤 알고리즘이 더 빠를지 알기 위해 더 분석해야 할 것이다.