[알고리즘] 선택 정렬 (Selection Sort) 이란?

선택 정렬 (Selection Sort) 란?

해당 순서에 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘.

해당 자리를 선택하고 그 자리에 오는 값을 찾는 방법이다.

 

 

과정 (오름차순)

1. 주어진 배열 중에서 최솟값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교환한다.

3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교환한다. 이를 반복한다.

 

 

Python Code

def selection_sort(arr):
    n = len(arr)
    index_min = 0

    for i in range(n):
        index_min = i
        for j in range(i+1, n): # 최소 값의 위치를 찾는다.
            if arr[j] < arr[index_min]:
                index_min = j
        
        temp = arr[index_min]   # 최소값을 가진 원소와 i번째 원소를 교환한다.
        arr[index_min] = arr[i]
        arr[i] = temp

    print(arr)

selection_sort([5,4,3,2,1])

 

 

시간복잡도

첫 번째 회전에서 비교 횟수 : 1 ~ (n-1) = n-1

두 번째 회전에서 비교 횟수 : 2 ~ (n-2) = n-2

...

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

n개의 주어진 배열을 정렬하는데 O(n^2) 의 시간이 걸린다. 최선, 평균, 최악인 경우 모두 O(n^2) 으로 동일하다.

 

 

공간복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n)이다.

 

 

장점

- bubble sort와 동일하게 알고리즘이 단순하다.

- 정렬을 위한 비교 횟수는 많지만, bubble sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서는 비교적 효율적이다.

- bubble sort와 동일하게 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간이 필요하지 않다.

 

 

단점

- 시간 복잡도가 O(n^2) 으로, 비효율적이다.

- 불안정 정렬(Unstable Sort)이다.

* 불안정 정렬 : 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘