[코드트리 조별과제] 삽입 정렬 구현

 

 

---

 

 

---

 

문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

 

 

수도 코드

function insertion_sort(arr[])
  set result = 0
  set size = arr.size
  for i = 1 ... i < size
    set j = i - 1 
    set key = arr[i]
    while j >= 0 && arr[j] > key
      arr[j + 1] = arr[j]
      j--
      result += 1
    arr[j + 1] = key
    
  return result

 

 

 

 

코드(Python)

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
for elem in arr:
    print(elem, end=" ")

 

 

 

코드 설명

먼저 key를 설정하여 해당 키 앞 부분까지는 정렬이 되어 있다고 가정한다.
key부터 마지막 인덱스까지, 앞부분 원소들과 비교하여 알맞은 위치로 이동한다.
최악의 경우 n-1개의 원소가 이동해야하므로 최대  O(N^2)의 시간복잡도를 가진다.