모두의 알고리즘 문제 09. 삽입 정렬 연습 문제

9-1 일반적인 삽입정렬 알고리즘을 사용해서 리스트[2, 4, 5, 1, 3]을 정렬하는 과정 서술

 

문제09 삽입정렬 이론공부 포스팅에 자세히 적어놨음.

 

9-2 정렬 알고리즘을 오름차순에서 내림차순으로 바꿔라.

 

def insert_sort(a):
    n=len(a)
    for i in range(1, n): # 1부터 n-1까지
        key=a[i] #i번 위치에 있는 값을 key에 저장
        j=i-1 #j를 i 바로 왼쪽 위치에 저장
        #리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j>=0 and a[j] < key:
            a[j+1]= a[j] #삽입할 공간이 생기도록 값을 오른쪽으로 한칸 이동
            j-=1
        a[j+1] = key #찾은 삽입 위치에 key를 저장
        
        
d = [2, 4, 5, 1, 3]
insert_sort(d)
print(d) #결과 [5, 4, 3, 2, 1]

while문의 등호만 바꾸면 된다. 기준을 키보다 큰 것으로 할지 작은 것으로 할지에 따라서 오름차순, 내림차순이 결정된다.