[Python]Selection Sorting

i번째 인덱스를 최소값으로 선택하고, i+1부터 순회하면서 i보다 작은 값을 가진 인덱스 위치가 발견되면 swap 한다

장점은 구현하기 간단하고 비교 및 교환의 횟수가 버블, 삽입 정렬보다 적다는 특징을 가진다.

단점은 성능이 O(N^2)으로 좋지 않다.

 

정리

• 첫 인덱스부터 끝 인덱스까지 순회
• Min Index 공간 1개 필요, 저장
• 현재 인덱스 값과 Min Index 스왑

def selection_sort(arr):
    for i in range(len(arr)):
        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]
    return arr