[Python] 선택정렬

선택정렬

데이터에서 최솟값을 찾아 그 값과 범위의 맨 앞에 있는 값을 서로 바꾸는 과정을 반복하는 알고리즘이다.

 

선택정렬 과정

예를 들어 [2, 4, 5, 1, 3] 가 있을 때, 가장 작은 값을 찾아 첫번째 값과 그 값을 바꾼다.

(이미 정렬 완료된 값은 | 로 구분한다.)

[2, 4, 5, 1, 3] # 가장 작은 값 : 1 <-> 첫번째 값 : 2

[1 | 4, 5, 2, 3] # 가장 작은 값 : 2 <-> 첫번째 값 : 4

[1, 2 | 5, 4, 3] # 가장 작은 값 : 3 <-> 첫번째 값 : 5

[1, 2, 3 | 4, 5] # 가장 작은 값 : 4 <-> 첫번째 값 : 4 //변화없음

[1, 2, 3, 4 | 5] # 자료가 5 하나만 남음. 종료


결과 [1, 2, 3, 4, 5]

 

선택정렬 알고리즘

def sel_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]
        print(a)
            
d = [2, 4, 5, 1, 3]
sel_sort(d)
print(d)

참고

파이썬은 두 자료의 값을 바꿀때 다음과 같이 쉼표를 이용해 변수를 뒤집는 방법을 사용한다.

예를 들어 x와 y의 값을 바꿀 때 x, y = y, x 를 사용하면 쉽게 바꿀 수 있다.

 

선택정렬의 시간복잡도는 O(N^2)이다.