선택 정렬 (Selection Sort)

 

선택 정렬은 정렬되지 않은 배열에서 반복적으로 최소값을 가지는 원소(오름차순 정렬의 경우)를 찾아 배열의 맨 앞자리에 높음으로써 정렬하는 방식이다. 선택 정렬은 원 배열을 두 개의 서브 배열로 나눈다.

 

1) 이미 정렬되어 있는 서브 배열

2) 정렬되어 있지 않은 나머지 서브 배열. 선택 정렬을 순회하는 매 차수마다 최소값을 가지는 원소가 해당 서브 배열에서 선택되어 이미 정렬되어 있는 1번 서브 배열로 옮겨진다.

 

공간복잡도: O(n)

시간복잡도: O(n^2)

 

 

코드>

 

def selection_sort(array):
    for idx in range(len(array)):
        min_idx = idx
        for j in range(idx+1, len(array)):
            if array[j] < array[min_idx]:
                min_idx = j
        (array[idx], array[min_idx]) = (array[min_idx], array[idx])
    return(array)

 

 

실행결과>

 

 

 

 

 

 

출처: https://www.geeksforgeeks.org/python-program-for-selection-sort/