Algorithm - Selection Sort

Selection Sort

 Bubble Sort와 유사한 알고리즘으로 주어진 배열 중 최솟값을 찾고, 그 값을 맨 앞에 위치한 값과 교체하는 알고리즘

 

구현

• 현재 index 값을 Min값에 저장하고, 현재 index 이후 배열의 요소와의 크기를 비교하여 다음 요소의 크기가 작다면(크다면) Min값 갱신
• 1회전을 수행하고 나면 현재 index값과 Min값의 위치를 교환
• 1회전을 수행하고 나면 가장 작은 요소(가장 큰 요소)가 맨 왼쪽 요소로 이동하므로, 다음 회전 때는 왼쪽 요소를 제외하고 회전 수행

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

 

공간 복잡도

별도의 추가 공간을 사용하지 않고 주어진 배열 원소의 위치만 바꾸기 때문에 O(1)

 

시간 복잡도

반복문을 통해 0부터 n-1의 인덱스에 접근해야 하기 때문에 O(n)의 시간을 소요하고,

한 인덱스의 루프에서는 주어진 배열 원소의 값의 대소 비교 후 자리 교환을 하기 위해 O(n)의 시간이 추가로 필요함

그래서 O(n^2)의 시간 복잡도를 가짐

인덱스가 n - 1일 때 n-1번, n-2일 때 n-2번...
(n-1) + (n-2) + ... + 1 = (n-1) * n / 2 = O(n^2)

 

장점

• 구현이 쉬움
• 코드가 직관적임
• 정렬을 위한 비교 횟수는 많지만, 실제 교환하는 횟수는 적기 때문에 Bubble Sort에 비해 조금 더 빠름

 

단점

• O(n^2)의 시간 복잡도를 가지기 때문에 효율적이지 않음

 

Bubble Sort와 비교

• Bubble Sort와 Selection Sort 둘 다 최악의 시간 복잡도는 O(n^2)을 가지지만, 버블 정렬은 처음부터 정렬된 배열이 들어오게 되면 1회전만 진행하기 때문에 O(n)의 시간 복잡도를 가질 수 있음
• 하지만, Selection Sort는 정렬을 위한 비교 횟수는 동일하게 많지만, 실제로 교환을 행하는 횟수는 적기 때문에 조금 더 빠르다는 장점을 가지고 있음
• Bubble Sort는 인접한 요소끼리 서로의 값을 비교하기 때문에 중복된 값의 순서가 변하지 않는 Stable 한 알고리즘이고, Selection Sort는 모든 요소를 탐색한 후에 마지막 최솟값과 변경시키기 때문에 Unstable 한 알고리즘

Stable / Unstable
정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 Stable
중복된 값들의 순서가 변하면 Unstable