[엘카데미 챌린지] 18일차 파이썬 알고리즘 (5)

1. 개요

오늘은 어제 쉽게 설명한 선택 정렬 알고리즘을 더 효율적으로 구현하는 방법에 대해 고민해보았고,

삽입 정렬 알고리즘 문제를 풀이하였다.

2. 문제

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

어제 쉽게 구현한 선택 정렬 알고리즘을 효율적으로 구현할 수 있는 일반적인 알고리즘을 구현해 보자.

리스트 a를 매개 변수로 받아 자료 값중 가장 최솟값을 차례대로 정렬해주는 함수 sel_sort를 작성하라.

 

풀이

일반적인 선택 정렬 알고리즘은 입력으로 주어진 리스트 a안에서 직접 자료의 위치를 정렬시키는 알고리즘이다.
처리할 대상 범위에서 최솟값을 찾아 그 값과 범위의 맨 앞에 있는 값을 서로 바꾸는 과정을 반복한다.
이 과정이 한 번 끝날 때마다 범위 안의 맨 앞에 있는 값은 정렬이 끝난 것이므로 정렬 대상 범위에서 제외한다.

 

def sel_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if a[j] < a[min_index]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]

# 예시 사용
d = [2, 4, 5, 1, 3]
sel_sort(d)
print(d)  # 출력 결과: [1, 2, 3, 4, 5]

 

---

2) 쉽게 설명한 삽입 정렬 알고리즘

리스트 a를 매개 변수로 입력 받아 삽입 정렬을 하여 리스트 result에 저장하여 반환하는 함수 ins_sort를 작성해라.

 

풀이

# 리스트 r에서 v가 들어가야 할 위치를 돌려주는 함수
def find_ins_idx(r, v):
    # 이미 정렬된 리스트 r의 자료를 앞에서부터 차례로 확인하여
    for i in range(0, len(r)):
        # v 값보다 i번 위치에 있는 자료 값이 크면
        # v가 그 값 바로 앞에 놓여야 정렬 순서가 유지됨
        if v < r[i]:
            return i
    # 적절한 위치를 못 찾았을 때는
    # v가 r의 모든 자료보다 크다는 뜻이므로 맨 뒤에 삽입
    return len(r)

# 리스트 a를 매개 변수로 입력 받아 삽입 정렬을 하여 리스트 result에 저장하여 반환하는 함수
def ins_sort(a):
    result = []  # 정렬된 결과를 저장할 리스트

    for value in a:
        insert_idx = find_ins_idx(result, value)  # 현재 값이 삽입될 위치 찾기
        result.insert(insert_idx, value)  # 값 삽입

    return result

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

1. 리스트 a에 아직 자료가 남아 있다면 → while a:
2. 남은 자료 중에 맨 앞의 값을 뽑아내기 → value = a.pop(0)
3. 그 값이 result의 어느 위치에 들어가면 적당할지 알아내기→ ins_idx = find_ins_idx(result, value)
4. 3번 과정에서 찾아낸 위치에 뽑아낸 값을 삽입 → result.insert(ins_idx, value)
5. 1번 과정으로 돌아가 자료가 없을 때까지 반복