알고리즘 - 선택 정렬 (Selection Sort)

알고리즘 - 선택 정렬 (Selection Sort)

제자리 정렬 알고리즘 중 하나로, 입력 데이터 이외에 다른 추가 메모리를 요구하지 않는다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 주어진 리스트 중에서 최소값을 먼저 찾고, 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트들을 같은 방법으로 끝까지 교체한다.

 

모든 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n^2)

 

[예시]

 

[Code]

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]