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

1. 개요

오늘은 정렬 알고리즘을 풀이하였다.

---

2. 문제

1) 순차 탐색 알고리즘

순차 탐색 알고리즘을 활용하여 리스트 a와 비교값인 변수 x를 받아 리스트 a의 원소와 x와 같다면 x를 반환하고 아닐 경우 -1를 반환하는 함수 search_list를 작성하세요.

 

풀이

def search_list(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

# 테스트 예시
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18))   # 2(순서상 세 번째지만, 위치 번호는 2)
print(search_list(v, 33))   # 3(33은 리스트에 두 번 나오지만 처음 나온 위치만 출력)
print(search_list(v, 900))  # -1(900은 리스트에 없음)

리스트에 있는 첫 번째 자료부터 하나씩 비교하면서 같은 값이 나오면 그 위치를 결과로 돌려주고, 리스트 끝까지 찾아도 같은 값이 나오지 않으면 -1을 돌려주면 된다.

 

2) 선택 정렬 알고리즘

선택 정렬 알고리즘을 활용하여 리스트 a를 매개 변수로 받아 a에 값이 남아 있을 때 까지 최소값을 찾아서 뽑아 리스트 result에 끝부터 저장하여 반환하는 함수 sel_sort를 작성해라. (find_min_idx() 함수를 사용해야 한다.)

# 주어진 리스트에서 최솟값의 위치를 돌려주는 함수
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:     # 주어진 리스트 a에 값이 남아있을 때까지 반복
        min_idx = find_min_idx(a)  # 남은 자료 중에서 최솟값의 위치를 검색
        value = a.pop(min_idx)     # 최솟값을 리스트 a에서 빼내어 value에 저장
        result.append(value)       # value를 result 리스트의 맨 끝에 추가
    return result  # 정렬된 리스트 result를 반환

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

알고리즘은 다음과 같다.

 

1. 리스트 a에 아직 자료가 남아 있다면 → while a:
2. 남은 자료 중에서 최솟값의 위치를 찾는다. → min_idx = find_min_idx(a)
3. 찾은 최솟값을 리스트 a에서 빼내어 value에 저장 → value = a.pop(min_idx)
4. value를 result 리스트의 맨 끝에 추가 → result.append(value)
5. 1번 과정으로 돌아가 자료가 없을 때까지 반복