[기술면접/알고리즘] Selection Sort

Selection Sort에 대해 설명하세요

Keyword

in-place sorting, 최솟값

---

Script

입력 배열 이외에 추가 메모리를 요구하지 않는 in-place sorting(제자리 정렬) 알고리즘 중 하나로, O(n^2)의 시간복잡도를 가지는 정렬 알고리즘입니다. 선택 정렬은 첫번째 index부터 해당 index를 기준으로 이후 index의 data와 비교하여 매 회전마다 최솟값을 초기 index 위치에 오도록 합니다. 이렇게 되면, 매 회전마다 가장 작은 값이 앞으로 오게 됩니다.

---

Additional

시간복잡도

비교 횟수
(n-1) 회전 => (n-1, n-2, ..., 2, 1) 개의 원소 중 최솟값 찾기
=> (n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

교환 횟수
매 회전(총 n-1번 회전) 마다 1번의 Swap
=> 3(n-1) 번

T(n) = O(n^2)

그림

코드 (python)

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

정렬 알고리즘 시간복잡도 비교