이중 선택 정렬 (Double Selection Sort)

1. Introduction

이중 선택 정렬은 한번의 루틴에서 최소값과 최대값을 같이 찾는 방식으로 정렬하는 선택정렬의 variation이다.

2. Approach

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

def double_selection(arr, a , b):
    start = a
    end = b
    while start < end:
        min = start
        max = end
        for i in range(start+1, end):
            if arr[i] < arr[min]:
                min = i
            if arr[i] > arr[max]:
                max = i
        
        arr[start], arr[min] = arr[min], arr[start]
        arr[end], arr[max] = arr[max], arr[end]
        start += 1
        end -= 1

 

3. Discussion

선택정렬의 variation이기 때문에, 이중 선택 정렬 역시 stable하며 in-place한 알고리즘이다.