쉽게 설명한 삽입 알고리즘

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

#리스트 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
    
    return len(r)
    #적절한 위치를 못찾았을때는 
    #v가 r의 모든자료보다 크다는 뜻이므로 맨뒤에 삽입

def ins_sort(a):
    result=[] #새리스트를 만들어서 값을 저장
    while a: #기존 리스트에 값이 남아있는 동안 반복
        value=a.pop(0) #기존 리스트에서 한개 꺼냄
        ins_idx=find_ins_idx(result,value) #꺼낸 값이 들어갈 적당한 위치 찾기
        result.insert(ins_idx,value) #찾은 위치에서 값삽입(이후 값은 한칸씩 밀려남)
                                      #ins_idx를 통해 찾아온 위치에다가 value 값을 넣는 거임.
    return result

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

print(ins_sort(d))

일반적인 삽입정렬 알고리즘

오름차순

# 일반적인 삽입정렬 알고리즘
#입력:리스트 a
#출력:없은(입력으로 주어진 a가 정렬됨-이게 return 값이 들어가면 출력 값이 정렬된 새리스트가 됨)

def ins_sort(a):
    n=len(a)
    for i in range(1,n): #1부터 n-1까지 그래야 끝까지 비교가능!
        key=a[i] #i번 위치에 있는 값을 key에 저장
        #j를 i 바로 왼쪽 위치로 저장
        j=i-1
        #리스트 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j>=0 and a[j]>key:
            a[j+1]=a[j]
            j-=1
            a[j+1]=key

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

print(d)

내림차순

#오름차순
def ins_sort(a):
    n=len(a)
    for i in range(1,n): #1부터 n-1까지 그래야 끝까지 비교가능!
        key=a[i] #i번 위치에 있는 값을 key에 저장
        #j를 i 바로 왼쪽 위치로 저장
        j=i-1
        #리스트 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j>=0 and a[j]<key: #다른데는 안건드리고 여기만 건드리면 된다.
            a[j+1]=a[j]
            j-=1
            a[j+1]=key

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

print(d)