오름차순 정렬(ascending sort) -2

삽입정렬 (insertion sort)

파이썬으로 작성해보았다.

# insertion sort
x = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
for j in range(1, len(x)):
    for i in range(j, 0, -1):
        if x[i] < x[i-1]:
            x[i], x[i-1] = x[i-1], x[i]

print(x)

• 현재 위치에서 왼쪽으로만 숫자의 크기를 비교하면서 한 칸 씩 정렬해 나가는 방식
• 나보다 작은 수를 만나면 그 자리에 위치한다(값이 제자리를 찾아가는 방식).
• 빅오 단계(시간복잡도) : O(N^2)
• 효율성
  : insertion sort > selection sort > bubble sort