[정렬] 선택 정렬 [Selection Sort]

선택 정렬에 대해 알아보자.

 

 

사진 출처

개념

 

정렬되지 않은 부분에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환한다.

이를 모두 정렬될 때까지 반복한다.

 

 

---

복잡도

 

버블 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다.

주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다.

 

가장 작은 원소를 앞에 계속 쌓아주기 위해 O(N)이 필요하고, 

가장 작은 원소를 찾기 위해 O(N)이 필요하다.

따라서 시간복잡도는 O(N^2)이다.

 

 

---

구현

 

def selection_sort(li):
    l = len(li)
    for i in range(l - 1):
        min_idx = i

        for j in range(i + 1, l):
            if li[j] < li[min_idx]:
                min_idx = j
        li[i], li[min_idx] = li[min_idx], li[i] # 가장 작은 원소를 정렬되지 않은 부분의 가장 앞의 원소와 swap

 

 

 

---

코드 참고