[Algorithm/Python] 선택 정렬(Selection Sort)이란? || Sort

📌 선택 정렬(Selection Sort)

선택 정렬

그림을 보면, 파란색으로 칠해진 수들 중 가장 작은 수를 골라, 빨간색으로 칠해진 수와 바뀌는 것을 확인해볼 수 있다.
이처럼, 선택 정렬은 가장 작은 수를 차례대로 선택하여 정렬하는 방식이다.
 

✅ CODE

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr[i] > arr[j]:
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
print(arr)

매번, 작은 수가 나올 때마다 위치를 바꿔주어 주도록 구현을 해보았는데, 작은 수가 나올 때마다 바꿔주는 것이 조금 비효율 적인 것 같다는 생각이 들었다.
 

✅ CODE

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
    min_index = i
    for j in range(i + 1, len(arr)):
        if arr[min_index] > arr[j]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
print(arr)

책을 참고하여 보니, 가장 작은 수가 담긴 인덱스만을 알아온 후, 스와핑하는 방식을 이용하여 구현해주었다.
 
구현된 코드를 보면, 이중 for문을 사용해주어 시간 복잡도는 $O(N^2)$이다.
 
참고) 이것이 코딩 테스트다 with 파이썬