UNIT 07 (정렬)

선택 정렬

문제) 주어진 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어라.

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

# 쉽게 설명한 선택 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
# 주어진 리스트에서 최솟값의 위치를 돌려주는 함수

def fine_min_dix(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 = fine_min_dix(a)
        value = a.pop(min_idx)
        result.append(value)
    return result


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

일반적인 선택 정렬 알고리즘

# 선택 정렬
# 입력 : 리스트 a
# 출력 : 없음(입력으로 주어진 a가 정렬됨)

def sel_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i] #위치 바꾸기


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

연습문제

7-1) 일반적인 선택 정렬 알고리즘을 사용해서 리스트 [2, 4, 5, 1, 3]을 정렬하는 과정을 적어라.
1, 4, 5, 2, 3
1, 2, 5, 4, 3
1, 2, 4, 5, 3
1, 2, 3, 5, 4
1, 2, 3, 4, 5

7-2) 프로그램 7-1과 7-2의 정렬 알고리즘은 숫자를 작은 수에서 큰 수 순서로 나열하는 오름차순 정렬이다. 이 알고리즘을 큰 수에서 작은 수 순서로 나열하는 내림차순 정렬로 바꾸려면 프로그램의 어느 부분을 바꿔야 하는가?
'<'를 '>'로 바꿔준다.

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10