Selection Sort (선택 정렬)

# Selection Sort
# 앞에서부터 원소를 하나씩 선택한 후, 그 뒷부분에서 최솟값을 찾아 그 둘을 swap하는방식으로 정렬하는 방식
# 시간복잡도: O(N^2) <- N(N-1)/2
# 공간복잡도: n
# 장점: 비교횟수는 많지만 bubble sort에 비해 자리를 교환하는 횟수가 적어 많은 교환이 일어나야 할 때(정렬이 많이 이루어져야 할 때) 효율적
# 추가 메모리를 필요로 하지 않는다(in-place). 
# 단점: unstable하다.

 

Python

def selection_sort(lst):
    for i in range(len(lst)-1):  # i = 정렬할 자리. 맨 마지막은 안 봐도 됨
        min_idx = i  # min_idx 은 i와 swap할 원소
        for j in range(i+1, len(lst)):
            if lst[min_idx] > lst[j]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]  # i 자리에 min_idx의 원소를 넣고 swap
    return lst

arr = [3, 9, 3, 1, 5]  # unstable의 예
print(selection_sort(arr))

 

Javascript

function selection_sort(arr) {
    for (let i=0; i<arr.length-1; i++) {
        let min_idx = i;
        for (let j=i+1; j<arr.length; j++) {
            if (arr[min_idx] > arr[j]) min_idx = j;
        }
        let tmp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = tmp;
    }
    
    return arr;
}