선택 정렬 (Selection Sort)

1. Introduction

선택정렬은 각 루틴마다 최소(최대)값을 찾아 정렬하는 방식의 정렬 알고리즘이다. 버블 정렬과 그 variation들과 같은 $O(n^2)$알고리즘이지만, 저들과는 궤를 달리한다.

2. Approach

다음 이미지는 선택 정렬의 과정을 시각화 한것이다. 출처는 위키피디아.

Example of Selection Sort

다음 코드는 파이썬에서 구현한 선택정렬이다.

def selection(arr, a, b):
    for i in range(a, b):
        min = i
        for j in range(i+1, b+1):
            if arr[j] < arr[min]:
                min = j
        
        arr[i], arr[min] = arr[min], arr[i]

3. Discussion

선택정렬은 stable한 정렬에 속하며 in-place한 알고리즘에 속한다.

선택 정렬의 한 variation으로 빙고 정렬 (Bingo Sort)라는 것이 있다. 최소(최대)값을 발견하고 swap할 때, 같은 값이 여러개있다면 한꺼번에 움직이는 정렬 알고리즘이다.

다음 코드는 파이썬에서 구현한 빙고 정렬이다.

def bingo(arr, a, b):
    max = b
    nextValue = arr[max]
    for i in range(b-1, a-1, -1):
        if arr[i] > nextValue:
            nextValue = arr[i]
    while (max > 0) and (arr[max] == nextValue):
        max -= 1

    while max > 0 :
        value = nextValue
        nextValue = arr[max]
        for i in range(max - 1, a-1, -1):
             if arr[i] == value:
                 arr[i], arr[max] =  arr[max], arr[i]
                 max -= 1
             elif arr[i] > nextValue:
                 nextValue = arr[i]
        while (max > 0) and (arr[max] == nextValue):
            max -= 1