선택정렬(Selection sort)

선택정렬

시간복잡도	공간복잡도
전체 요소를 순회하기 위해 N 요소들을 비교하며 가장 작은 요소를 찾기 위해 N N x N = O(N²)	비교 후 배열 내 스왑을 하기 위해 O(1)

 

배열을 순회하며 가장 작은 요소를 찾아 맨 앞에 위치시키는 방식의 정렬

 

[7, 4, 5, 1, 3]

 

예를 들어 이렇게 주어진 배열을 정렬한다고 해보자.

 

배열은 총 5개의 요소를 가지고 있다.

맨 앞의 요소부터 전체 요소와 비교해가며 가장 작은 요소를 찾아 비교요소와 위치를 바꾼다.

 

먼저 가장 작은 요소의 index를 0번으로 초기화한다.

 

첫번째 loop는 0번을 기준으로 비교한다.

0번과 1번, 0번과 2번, 0번과 3번, 0번과 4번하며, 만약 비교하는 요소가 가장 작은 요소(현재 0번)보다 더 작다면 가장 작은 요소의 인덱스로 바꿔준다. 이렇게 끝까지 비교하며 가장 작은 요소를 찾는다. 첫번째 loop가 끝나면 전체 배열 중 가장 작은 요소의 인덱스를 찾게 된다. 그러면 0번 요소와 가장 작은 요소의 값을 스왑해준다. 그리고 다음 loop로 넘어간다.

 

두번째 loop에서 0번은 더이상 비교할 필요가 없다. 가장 작은 요소이기 때문이다. 이제 두번째로 작은 요소를 찾기 위해 1번부터 다시 비교를 시작한다. 1번과 2번, 1번과 3번, 1번과 4번을 비교한다.

 

이런 식으로 하여 배열 길이 -1회만큼 전체를 순회하며 정렬한다. -1회를 하는 이유는 배열의 마지막 -1 번째 요소까지 비교했을 때 자연히 마지막 남은 요소는 가장 큰 요소이기 때문이다.

 

 

구현

def selection_sort(input_array):
    print(input_array)
    for i in range(len(input_array) - 1):
        min_index = i
        for j in range(i + 1, len(input_array)):
            if input_array[min_index] > input_array[j]:
                min_index = j
        input_array[i], input_array[min_index] = input_array[min_index], input_array[i]
        print(input_array)


if __name__ == '__main__':
    selection_sort([7, 4, 5, 1, 3])
    

[7, 4, 5, 1, 3]
[1, 4, 5, 7, 3]
[1, 3, 5, 7, 4]
[1, 3, 4, 7, 5]
[1, 3, 4, 5, 7]

 

  i는 이번 loop에서 몇 번 인덱스에 있는 요소를 기준으로 비교할지 결정한다. 앞서 말했듯 배열의 길이 - 1 번째 요소까지만 비교하면 마지막 요소는 비교할 필요가 없기 때문에 len(input_array) - 1 만큼 순회한다.

  i가 가장 작은 수라고 가정하고 min_index의 값을 i로 넣어준다. 그리고 이후 min_index의 요소를 배열의 마지막 요소까지 비교하며 가장 작은 수의 index를 찾는다.

  배열의 끝까지 모두 순회하여 가장 작은 수의 index를 찾았다면 i번째와 자리를 바꿔준다. 그리고 i번째 작은 값을 찾기 위해 다음 loop를 시작한다.

 

  pinrt된 배열을 보면 매 순회마다 가장 작은 값과 i번째 요소의 자리가 스왑되는 것을 확인할 수 있다.

 

 

  버블정렬과 비교하자면,

  버블정렬은 인접요소를 모두 찾으며, 최악의 경우 매 비교마다 스왑이 일어난다. 그리고 가장 큰 값을 뒤로 보내고 순회마다 가장 마지막 값은 비교할 필요가 없어진다.

  선택정렬은 선택된 요소와 이후 모든 요소를 비교하며, 순회가 끝난 후 가장 작은 값과 선택요소의 위치를 한번 스왑한다. 그리고 가장 작은 요소를 찾아 앞에서부터 채움으로써 앞의 값은 더이상 비교하지 않는다.

 

최적화

매 순회마다 요소를 선택하여 이후 모든 요소들과 비교하며 가장 작은 값을 찾아야하기 때문에 특별히 최적화를 할 수 없는 알고리즘이다.

 

 

참고

https://www.dalecoding.com/algorithms/selection-sort

선택 정렬 (Selection Sort) | 달레코딩