선택 정렬 (Selection Sort)

선택 정렬

선택 정렬은 처음부터 끝까지 하나씩 확인하며 제일 작은 값을 찾아 맨 앞으로 보낸 후

다시 두번째부터 끝까지 하나씩 확인하며 이번에 제일 작은 값을 두번째로 보내는 과정을 반복하는 정렬이다.

이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자

arr = [4, 6, 2, 9, 1]

# 0 1 2 3 4 1 2 3 4 2 3 4 3 4
def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i):
            print(i+j)
            
selection_sort(arr)

 

버블 정렬과 다른점은 '최솟값'을 찾아 변경한다는 부분이다. 

인덱스를 하나씩 돌며 제일 작은 값을 찾아 인덱스만 따로 min_i 변수에 저장한 뒤

내부의 반복문이 끝났을 때 최소 값의 인덱스와 i의 값을 변경해주면 되겠다. 

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_i = i			# 최소값에 대한 인덱스 따로 저장
        for j in range(n-i):
            if arr[min_i] > arr[i+j]:
                min_i = i+j		# 더 작은 수를 찾으면 그에 대한 인덱스 값을 min_i에 저장한다.
        arr[i], arr[min_i] = arr[min_i], arr[i]

    return arr
    
selection_sort(input)
print(input)

 

선택 정렬의 시간 복잡도

선택 정렬도 마찬가지로 2차 반복문이 나왔고, array의 길이 만큼 반복하므로 O(N²)의 시간 복잡도를 가진다.