정렬 - 3) 삽입 정렬 (insertion sort)

 

📍 삽입 정렬:

• 앞에서부터 순서대로 보면서, 앞에 있는 모든 원소가 정렬되어 있다는 가정 하에서 현재 원소의 위치를 적절하게 집어넣는 정렬
• 시간복잡도: O(N^2)
  • n 개의 원소에 대해 값 삽입을 수행하는데, 2번째 원소의 경우에는 최대 1개의 원소를 이동해야 하고, 3번째 원소의 경우에는 최대 2개의 원소를 이동해야 하며, n번째 원소까지 삽입하는 경우에는 최대 n-1개의 원소가 이동해야 함

 

---

 

💬 python 코드

• n 개의 원소가 주어졌을 때, 삽입 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬

n = int(input())
arr = list(map(int, input().split()))

for i in range(1, n):
    
    key = arr[i]
    j = i-1

    while j >= 0 and arr[j] > key: # i 값보다 이전 idx 값이 더 크면
        arr[j+1] = arr[j] # 한 칸 밀고 (큰 값을 뒤로 보냄)
        j -= 1
    
    arr[j+1] = key # 멈춘 위치에 key 입력
print(*arr)