[python]선택 정렬

선택 정렬(Selection sort)이란?

---

리스트 중에서 가장 작은 걸 선택한 뒤에 가장 앞으로 보내면서 정렬하는 방법.

1. 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 값과 교체한다.
3. 맨 앞의 값을 제외하고 다시 검색해서 최소값을 찾는다.
4. 맨 앞의 값 뒤에 값과 최소값을 교체한다.
5. 차례로 반복

직관적으로 애니메이션 이미지를 보면서 예를들어보자.

옆에 [8,5,2,6,9,3,1,4,0,7]이라는 배열이 있다. 가장 처음에 앞에서부터 찾아가며 최소값 0을 찾아내고 이를 맨 앞에 있는 0과 교환한다. [0,5,2,6,9,3,1,4,8,7] 그 다음에 0을 제외하고 검색을 시작하고 최소값 1을 찾아낸 뒤에 5와 1을 교환한다. [0,1,2,6,9,3,5,4,8,7] 그 다음에 0,1을 제외하고 검색을 시작하고 최소값 2를 찾아낸다. 근데 2 이외에 최소값은 더이상 없으므로 2는 그냥 그 자리에 있게 된다. 이런 식으로 계속 내려가다가 결국 [0,1,2,3,4,5,6,7,8,9]로 리스트가 정렬된다.

선택 정렬 알고리즘의 특징

---

장점

• 이해하기 쉽고 간단하다.

 

단점

• 입력 크기가 커지면 커질수록 정렬하는 데 시간이 굉장히 오래 걸림

한마디로 단순하지만 비효율적이다.

선택 정렬 시간복잡도

---

하나씩 비교해야하므로 n개의 자연수의 합을 구하는 시그마 공식과 같다.

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

따라서 빅오표기법으로 표현하면 최악의 경우를 가정하기 때문에 n제곱만 남아서 O(N²)

코드

---

# 선택 정렬
# 리스트 a를 정렬하기

def sel_sort(a):
    n = len(a) #배열 a의 갯수
    for i in range(n-1):
        min_idx = i #인덱스 초기값으로 첫번째 배열을 넣어둔다
        for j in range(i+1,n): #배열 두번째 값부터 배열의 갯수만큼
            if a[j] < a[min_idx]:
                min_idx = j #찾은 값이 최솟값이면 그 찾은 값의 인덱스를 min_idx에 넣는다
        a[i],a[min_idx] = a[min_idx],a[i] #찾은 최솟값을 i위치와 교환한다
    return a #어차피 매게변수로 들어온 리스트 값 자체를 바꾸므로 리턴을 생략해도 출력되는 것은 같다
a = [8,1,3,4,5,2,6,7]
sel_sort(a)
print(a)

여기서 두 자료 값을 서로 바꾸는데 <code<a[i], a[min_idx] = a[min_idx],a[i] 가 쓰였다.

다른 언어는 두 값을 바꾸기위해서 제 3의 임시 변수를 만들어 두 값을 교환했야 하는데.

파이썬에서는 x,y = y, x 이렇게 간단하게 두 값을 교환하는 문법을 제공한다.

참고로 만약 리스트를 오름차순 정렬이 아니라 내림차순으로 정렬하기 위해서는 이중for문의 안에 for문의 부등호를 반대로 if a[j] > a[min_idx] 이렇게 바꾸어주면 된다.