[알고리즘] 삽입 정렬

* <모두의 알고리즘 with 파이썬>의 문제 09를 정리한 내용입니다.

 

1. 삽입 정렬이란? 

• 자신보다 앞의 원소가 큰지 작은지 확인하여 자신의 위치를 찾아 '삽입'하는 알고리즘이다.
• 정렬되어 있는 경우는 비교를 하지 않기 때문에 버블 정렬과 달리 불필요한 비교가 줄어들었다.

 

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

def ins_sort(a):
    n = len(a)
    for i in range(1, n):  # 앞 원소와 비교해야하기 때문에 가장 앞 원소는 무시한다
        key = a[i] # 기준 원소
        j = i - 1 # 바로 하나 앞 원소
        
        while j >=0 and a[j] > key: # 앞 원소가 나보다 클 경우만 위치 변경
            a[j+1] = a[j] # a[j+1]는 기준 원소
            j -= 1 # 한 칸씩 앞으로 전진하며 비교 
        
        a[j+1] = key  # 삽입할 위치
    return a 

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

 

 

 

3. 위의 알고리즘은 오름차순 정렬이었습니다. 이를 큰 수에서 작은 수 순서로 나열하는 내림차순 정렬로 바꾸려면 프로그램의 어느 부분을 바꿔야 할까요? 

def ins_sort(a):
    n = len(a)
    for i in range(1, n):  # 앞 원소와 비교해야하기 때문에 가장 앞 원소는 무시한다
        key = a[i] # 기준 원소
        j = i - 1 # 바로 하나 앞 원소
        
        while j >=0 and a[j] < key: # 앞 원소가 나보다 작을 경우만 위치 변경
            a[j+1] = a[j] # a[j+1]는 기준 원소
            j -= 1 # 한 칸씩 앞으로 전진하며 비교 
        
        a[j+1] = key  # 삽입할 위치
    return a 

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

• while문의 조건을 수정해주었다. 기존 while문은 앞 원소가 나보다 클 경우에만 앞으로 옮겼다. 알고리즘 정의를 내림차순으로 바꾼다면, 앞 원소가 나보다 작을 경우에만 기준 원소를 앞으로 옮기면 된다.