모두의 알고리즘 문제08. 선택 정렬, 파이참에서 오류나는 경우

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

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) # 자료를 지정한 위치에서 빼내면서 그 값을 함수의 결괏값으로 돌려줌. 위치 지정 안하면 맨 마지막 값 반환.
        result.append(value) #자료를 리스트 맨 뒤에 추가
    return result

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

결과: [1, 2, 3, 4, 5, 9]

 

 

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

 

def sel_sort(a):
    n=len(a)

    for i in range(0, n-1): #0부터 n-2까지 반복
        min_idx=i
        for j in range(i+1, n): #1부터 n-1까지 반복
            # i=0일 때 1~n-1까지 비교해서 최솟값 a[i]에 저장, i=1일 때 2~n-1까지 비교해서 반복.
            if a[j] < a[min_idx]:
                a[i], a[j]= a[j], a[i] # 두 변수의 값을 교환


d = [2, 4, 5, 1, 3]

sel_sort(d)
print(d)

결과: [1, 2, 3, 4, 5]

 

교재에 나온대로 파이참에서 돌리면 일반적인 선택 정렬 알고리즘은 에러가 나서 위의 코드는 내가 수정한 코드다.

 

교재의 코드는 계속 코드는 맞는데 값이 이상하게 나와서 고민하다가 변수값이 너무 자주 바뀌어서 제대로 안지워져서 그랬다는걸 알았다. C언어로 프로그램 만들때 몇번 겪어봐서.

 

교재에 작성된 코드는 아래와 같다.

 

def sel_sort(a):
    n=len(a)

    for i in range(0, n-1): #0부터 n-2까지 반복
        min_idx=i
        for j in range(i+1, n): #1부터 n-1까지 반복
            # i=0일 때 1~n-1까지 비교해서 최솟값 a[i]에 저장, i=1일 때 2~n-1까지 비교해서 반복.
            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)

이런식으로 프린트문을 삽입해서 어떻게 오류가 나는지 살펴보고 스택오버플로에도 질문해서 문제점을 찾아볼 생각이다. 일단 그러려면 퇴근하고 밤에 가능하니 구청에 있는 지금은 할 수 있는 다른 공부를 우선 해야겠다.

def sel_sort(a):
    n=len(a)
    print("start", 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
                print("change", i, j)
                a[i], a[min_idx]= a[min_idx], a[i]
                print(a)


d = [2, 4, 5, 1, 3]

sel_sort(d)