파이썬] 선택정렬 Selection sort

쉽게 설명한 선택 정렬 알고리즘

def find_min_idx(a):
    n = len(a)
    min_idx = 0
    for i in range(1, n):
        if a[i] < a[min_idx]:
            min_idx = i
    return min_idx

def sel_sort(a):
    result = [] 	# 새 리스트를 만들어 정렬된 값을 저장
    while a:    	# 주어진 리스트에 값이 암아 있는 동안 계속
        min_idx = find_min_idx(a)# 리스트에 남아 있는 값 중 최솟값의 위치
        value = a.pop(min_idx)  # 찾은 최솟값을 빼내어 value에 저장
        result.append(value)    # value를 결과 리스트 끝에 추가
    return result

d = [2, 4, 5, 1, 3]
print(sel_sort(d))

일반적 선택 정렬 알고리즘(오름 차순)

def sel_sort(a):
    n = len(a)
    for i in range(0, n-1): # 0부터 n-2까지 반복
        # i 번 위치부터 끝까지 자료 값 중 최솟값의 위치를 찾음
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
                # 찾은 최솟값을 i번 위치로
        a[i], a[min_idx] = a[min_idx], a[i]

d = [1, 4, 5, 2, 3]
sel_sort(d)
print(d)

일반적 선택 정렬 알고리즘(내림 차순)

def sel_sort(a):
    n = len(a)
    for i in range(0, n-1): # 0부터 n-2까지 반복
        # i 번 위치부터 끝까지 자료 값 중 최솟값의 위치를 찾음
        max_idx = i				  	# 수정1
        for j in range(i+1, n):
            if a[j] > a[max_idx]:		# 수정2
                max_idx = j				# 수정3
                # 찾은 최솟값을 i번 위치로
        a[i], a[max_idx] = a[max_idx], a[i] # 수정4

d = [1, 4, 5, 2, 3]
sel_sort(d)
print(d)