알고리즘 with 파이썬(1) - 선택정렬

선택정렬은 첫번째 인덱스 부터 시작하여 뒤에 남은 값들과 하나씩 비교한다.

남은 값들 중 가장 큰(혹은 작은) 값이 정해지면 비교기준인 인덱스와 자리를 바꿔주는 방식

- 리스트 안의 자료를 한번씩 비교하기 때문에 계산 복잡도는 O(n²)

- 이해하기 쉽고 간단하지만, 비교횟수가 입력크기의 제곱에 비례하기 때문에 입력크기가 커지면 시간이 오래걸린다.

def sel_sort(a):
    n = len(a)
    for i in range(0,n-1): #n-2까지 확인
        min_idx = i # i번 위치부터 끝까지 자료값중 최솟값의 위치를 찾음
        for j in range(i+1,n):
            if a[min_idx]> a[j]:
                min_idx =j
        a[i], a[min_idx] = a[min_idx],a[i] # 찾은 인덱스와 i 인덱스 자리바꿔주기 (이게 되다니)
    print(a)

heights = [164,158,182,179,162,155,184,171]

sel_sort(heights)

 

* n-2 까지 확인하는 이유: 어차피 맨 마지막 값은 마지막 -1 인덱스 차례에서 비교 되었다.

** PYTHON에서 두 변수 끼리 바꾸는 방식에 매우 충격받았다.

 예제에서

a[i], a[min_idx] = a[min_idx],a[i] 

이렇게 배열간 값을 바꿔준것 처럼 쉼표를 기준으로 자리를 바꿔주면 된다 !

 

x =1 , y=2 일 때

x, y = y,x 라고 선언해주면

x = 2, y=1 값으로 변경되어있는 걸 확인 할 수 있다. (충격)