선택 정렬

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

총 2개의 함수가 필요하다.
첫번째는 최소값을 가지고 있는 인덱스를 찾는 함수
- for
두번째는 최소값을 지닌 리스트를 순서대로 쌓는 함수
- while
- pop
- append

---

# 가장작은 값을 지닌 값의 인덱스를 찾는 프로그램
def find_min_idx(num) :
    len_num = len(num)
    min_idx = 0 # 초기 인덱스를 줌
    for i in range(1,len_num) : # 초기 인덱스 0과의 비교는 할 필요없으니 1부터 시작
        if num[i] < num[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) # .pop(인덱스)
        result.append(value) # 
    return result

# 가장작은 값을 지닌 값의 인덱스를 찾는 프로그램
def find_min_idx(num) :
    len_num = len(num)
    min_idx = 0 # 초기 인덱스를 줌
    for i in range(1,len_num) : # 초기 인덱스 0과의 비교는 할 필요없으니 1부터 시작
        if num[i] < num[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) # .pop(인덱스)
        result.append(value)
    return result

 

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

앞서 쉽게 설명한 선택 정렬 알고리즘에선 리스트a에서 자료를 하나씩 꺼내서 다시 result에 넣는 방식이었으나 지금하게 되는 일반적인 선택 정렬 알고리즘에선 더 효율적인 정렬이 가능하다

---

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 # 최솟값을 min_idx에 저장
            a[i], a[min_idx] = a[min_idx], a[i] # 찾은 최솟값과 비교한 값의 위치를 바꿈. 이 과정을 반복하여 sort함수구현

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 # 최솟값을 min_idx에 저장
            a[i], a[min_idx] = a[min_idx], a[i] # 찾은 최솟값(min_idx)을 i번 위치로 서로 바꿈

삽입 정렬

하나를 끄집어내서 리스트전체와 비교하여 자신의 위치에 삽입함

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

# 쉽게 설명한 삽입 정렬
# 입력 : 리스트 a
# 출력 : 정렬된 새 리스트

# 리스트 에서 new_num가 들어가야 할 위치를 돌려주는 함수
def find_ins_idx(list_num,new_num) :
    for i in range(0,len(list_num) :
        if new_num < list_num[i] :
            return i # 인덱스를 돌려주어 이 위치에 들어가도록 함
    # 적절위치없을 때는 가장 크다는 의미이므로 맨 뒤에 삽입
    return len(list_num) # 리스트의 길이가 곧 해당 삽입값의 인덱스 위치.
# 즉, 리스트길이가 4인 배열의 인덱스는 [0] ~ [3]이므로 인덱스가 [4]이면 마지막인덱스[3]보다 높은것

def ins_sort(a) :  
    result = []
    while a :  # 리스트a에 아직 자료가 남았다면
        value = a.pop(0)
        ins_idx = find_ind_idx(result,value)
                   result.insert(ins_idx, value)
    return result

# 쉽게 설명한 삽입 정렬
# 입력 : 리스트 a
# 출력 : 정렬된 새 리스트

# 리스트 에서 new_num가 들어가야 할 위치를 돌려주는 함수
def find_ins_idx(list_num,new_num) :
    for i in range(0,len(list_num) :
        if new_num < list_num[i] :
            return i # 인덱스를 돌려주어 이 위치에 들어가도록 함
    # 적절위치없을 때는 가장 크다는 의미이므로 맨 뒤에 삽입
    return len(list_num) # 길이 인덱스를 줌으로써 가장 뒤에 인덱스를 삽입할수있게함?

def ins_sort(a) : 
    result = []
    while a : # 리스트a에 아직 자료가 남았다면 반복. 즉, 리스트 a를 비우고 새 리스트를 채운다는 의미.
        value = a.pop(0)
        ins_idx = find_ind_idx(result,value)
                   result.insert(ins_idx, value)
    return result