[Algorithm] 선택 정렬 (Selection Sort)

 

 

선택 정렬 (Selection Sort)

선택 정렬은 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시키며 정렬하는 알고리즘

 

 

 

작동 방식

• 인덱스 i에 들어갈 값은 인덱스 i부터 N(마지막 인덱스)까지 중 최소값이 된다.

예시

• 배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.

1. 5 3 8 1 2
2. 1 3 8 5 2
3. 1 2 8 5 3
4. 1 2 3 5 8
5. 1 2 3 5 8

시간 복잡도 : O(n^2)        * (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2

 

 

 

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