[알고리즘] 삽입 정렬

1. 삽입 정렬 의미
2. 삽입 정렬 개념
3. 삽입 정렬 예시
4. 삽입 정렬 구현 (With Python3)

 

삽입 정렬 의미

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

 

삽입 정렬 개념

• 삽입 정렬은 정렬하고자 하는 리스트의 크기가 n이라면 n-1번 반복하여 key 값을 기준으로 삽입할 위치를 찾아 반복하는 알고리즘
• 삽입 정렬의 첫 번째 시작은 두 번째 값이 key가 되어 첫 번째 값과 비교하여 첫 번째 값보다 작은 경우 첫 번째 값은 뒤로 밀리고 key가 첫 번째로 이동한다.
• 두 번째 바퀴에서는 세 번째 값이 key가 되고 두 번째 값과 비교하여 작은 경우 서로 위치를 교환한다. 이때 key는 두 번째 값이 되고 이제 key는 첫 번째 값과 비교해서 작은 경우 서로 위치를 교환한다.
• 위의 케이스를 계속 반복하여 오름차순으로 정렬을 실행한다.

 

삽입 정렬 예제

• 삽입 정렬을 이용하여 [5,4,2,1,3]을 오름차순으로 정렬시

삽입 정렬 예시

• 첫 번째 바퀴에서는 두 번째 값인 4가 key가 되어 첫번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다.
• 두 번째 바퀴에서는 세 번째 값인 2가 key가 되어 두번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 이후 key는 첫번째 값인 4와 비교해서 값이 더 작으므로 서로의 위치를 교환한다.
• 세 번째 바퀴에서는 네 번째 값인 1이 key가 되어 세번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 그 다음 key는 두번째 값인 4와 비교하여 값이 더 작으므로 서로의 위치를 교환한다. 마지막으로 key는 첫번째 값인 2와 비교해서 값이 더 작으므로 서로의 위치를 교환한다.
• 네 번째 바퀴에서는 다섯번째 값인 3이 키가 되어 네번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 그다음 key는 세번째 값인 4와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 그 다음 key는 두 번째 값인 2와 비교했을 때 값이 더 크므로 그 상태를 유지하면서 정렬이 종료된다.

 

삽입 정렬 구현 (With Python3)

def insertionSort(x):
    
    for i in range(1, len(x)):
        key = x[i]
        j = i - 1 # 이전 인덱스 값 
        while x[j] > key and j >= 0: # 이전 인덱스 값이 key보다 작고 인덱스가 리스트의 범위를 벗어나지 않을 경우
            x[j+1] = x[j]
            j -= 1
        x[j+1] = key
            
    return x
    
if __name__ == "__main__":
    
    x = [5,4,2,1,3]
    
    insertionSort(x)

 

삽입 정렬 특징

• 시간 복잡도
  • 반복을 두번 실행하므로 $$ O(n^2) $$
  • 이미 정렬이 된 상태라면 $$ O(n) $$