selection sort

내가 구현한 방법과 정식 알고리즘을 비교해보자

# selection
def selection_sort_not_good(a):  # 이 방법은 swap을 원래 방법보다 많이 하게 된다. 또한 insertion에 가까운 방법이다.
    n = len(a)
    for i in range(0, n - 1):
        for j in range(i + 1, n):
            if a[j] < a[i]:
                a[i], a[j] = a[j], a[i]
 
 
def selection_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[min_idx] > a[j]:  # i 뒤의 애들을 전부 흝고 그 중 하나를 골라서 swap
                min_idx = j
 
        a[i], a[min_idx] = a[min_idx], a[i]  # swap
 

원래의 방법은 기준이 되는 것 뒤의 애들을 한번 다 흝고 그 중 가장 작은 index와 swap하는 방식이지만 ,

시도하려던 방식은 기준위치의 값보다 작은 값을 발견하면 그대로 swap해서 불필요한 연산을 하게되어 시간이 더 많이 걸린다. 또한 insertion방식에 더 유사한 방법이라고 볼 수도 있다.