[알고리즘] 선택 정렬이란? (개념, 파이썬 코드)

선택 정렬(Selection Sort)이란?

배열의 각 위치마다 어떤 원소를 넣을지 선택하는 알고리즘

• 방법
  • 주어진 배열 중 최소값을 찾는다.
  • 그 값을 첫 번째 원소와 교체한다.
  • 첫 번째 원소를 제외하고 위 작업을 반복한다.

버블 정렬과 유사한 알고리즘이다.

(참고 글 : 버블 정렬이란?)

 

파이썬으로 구현하기

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

    for i in range(n-1):
        min_idx = i

        # i ~ n-1 구간 중 가장 작은 값의 위치를 찾는다.
        for j in range(i, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        # 가장 작은 값을 arr[i] 위치로 이동시킨다.     
        arr[i], arr[min_idx] = arr[min_idx], arr[i]


if __name__ == "__main__":
    arr = [1,6,4,2,3,5]

    print(f"before : {arr}")  # 정렬 전 리스트
    selection_sort(arr)
    print(f"after : {arr}")  # 정렬 후 리스트

 

시간복잡도

입력 리스트의 원소가 n개인 경우,

선택 정렬의 연산 횟수는 다음과 같다.

• 1번째 작업 : n번 비교
• 2번째 작업 : n-1번 비교
• ...
• n번째 작업 : 1번 비교

(n) + (n-1) + (n-2) + ... + (1) = n(n-1)/2 이므로,

O(n^2)의 시간이 소요된다.