Selection Sort (선택정렬)

Selection Sort (선택정렬)

선택정렬은 정렬되지 않은 부분에서 가장 최소의 값을 찾아 시작부분에 배치하여 정렬하는 알고리즘입니다.

O(n^2)의 시간복잡도를 가지며 알고리즘이 단순하여 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다.

Selection Sort 정렬과정

1. 주어진 배열에 최소 값을 찾습니다.
2. 그 값을 맨 처음에 위치한 값과 교체합니다.
3. 맨 처음 위치를 제외한 나머지 배열을 같은 방법으로 정렬합니다.

초기상태: (5 3 4 2 1 7 6)

Array	최솟값
(5 3 4 2 1 7 6)	1
(1 3 4 2 5 7 6)	2
(1 2 4 3 5 7 6)	3
(1 2 3 4 5 7 6)	4
(1 2 3 4 5 7 6)	5
(1 2 3 4 5 7 6)	6
(1 2 3 4 5 6 7)

Selection Sort 코드 (Python)

def selection_sort(arr):
    length = len(arr)
    for i in range(length-1):
        min_idx = i
        for j in range(i+1, length):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr