[정렬] Selection Sort - JS, Python

선택정렬 알고리즘

1. 먼저 주어진 리스트 중에 최소값찾기

2. 그 값(최소값)을 맨 앞에 위치한 값과 교환

3. 맨 앞을 고정하고 다시 순회하며 최소값 찾기

4. 그 값을 고정 값 바로 다음 위치와 교체...반복

 

 

 

 

선택정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 고정된다

교환 횟수를 최소화하는 반면 각 자료 비교하는 횟수 증가

 

Big O

* 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내줘야 함
* 구현 방식에 따라 사소한 오차는 있을 수 있지만 전체 연산횟수는 아래와 같음
   N + (N - 1) + (N - 2) + ... + 2
* 이는 (N^2 + N - 2) / 2 로 표현할 수 있는데 빅오 표기법에 따라서 O(N^2)이라 작성

 

WORST O(n^2) - 정렬이 하나도 안되어 있는 경우

BEST O(n^2) - 이미 정렬이 되어있는 경우 (비교 횟수)

 

선택정렬은 이미 정렬되어 있는 경우에도 O(n^2)의 시간복잡도를 가진다

이유는 매번 정해진 자리에 올 수 있는 최소값을 찾아야하기 때문 => 성능이 떨어짐

 

장점

in place알고리즘이기 때문에 메모리가 절약된다

직관적이므로 이해하기 쉽고 구현하기 쉽다

 

* in place란?

자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻

단점

최선의 경우에도 최악의 경우에도 O(n^2)라는 시간이 걸리는 만큼 성능이 매우 떨어짐

더 많은 비교가 필요하므로 비용이 많이 듦

 

Python 코드

# 선택정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_idx = i # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_idx] > array[j]:
            min_idx = j
    array[i], array[min_idx] = array[min_idx], array[i] # 스와프

print(array)

JS 코드

// 선택 정렬
let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for (let i = 0; i < array.length-1; i++) {
    let min_idx = i
    for (let j = i+1; j < array.length; j++) {
        if (array[min_idx] > array[j]) {
            min_idx = j
        }
    }
    if (min_idx !== i) {
        let swap = array[min_idx]
        array[min_idx] = array[i]
        array[i] = swap
    }
    console.log(`${i} 회전 : ${array}`)

}
return array;