선택정렬 (Selection Sort)

📌 선택정렬 (Selection Sort)

주어진 리스트에서 가장 작은 값을 찾고 그 값을 맨 앞에 있는 값과 교체한다.

그리고 맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체하는 방법이다.

버블 정렬과 마찬가지로 O(n^2)의 시간복잡도를 갖는다.

 

👉 과정

 [3, 4, 2, 5, 1]

최소값인 1과 3 swap

 

[1, 4, 2, 5, 3]

최소값 2와 4 swap

 

[1, 2, 4, 5, 3]

최소값 3과 4 swap

 

[1, 2, 3, 5, 4]

최소값 4와 5 swap

 

[1, 2, 3, 4, 5]

남은 숫자가 5 하나 남았기 때문에 자동으로 5가 최소값이 된다.

 

[1, 2, 3, 4, 5]

정렬 끝

 

 

👉 구현

def selection_sort(arr):
    for i in range(len(arr)):
        lowest = i

        for j in range(i + 1, len(arr)):
            if arr[j] < arr[lowest]:
                lowest = j

        if i != lowest:
            arr[i], arr[lowest] = arr[lowest], arr[i]

    return arr

 

👉 swap 수를 적게

버블정렬은 두 수를 비교해서 루프가 끝날 때까지 스왑을 하지만 선택정렬은 최소값을 찾아 swap을 하기 때문에 루프당 1번의 swap으로 버블정렬보다는 더 적은 swap을 한다.