[알고리즘] Insertion Sort

Insertion Sort

처리되지 않은 데이터 중 하나씩 골라 적절한 위치에 삽입하는 알고리즘

---

Process

1. 먼저 두번째 데이터와 첫번째 데이터의 대소를 비교해 두번째 원소가 더 작다면 교환한다

2. 다음 인덱스는 이전 데이터들과 비교해 적절한 위치에 둔다

---

Code

numbers = []
length = 100

for i in range(length, 0, -1):
    numbers.append(i)

for idx, num in enumerate(numbers):
    for n_idx in range(idx, 0, -1):
        if numbers[n_idx] < numbers[n_idx - 1]:
            numbers[n_idx], numbers[n_idx - 1] = numbers[n_idx - 1], numbers[n_idx]
        else:
            break

print(numbers)

---

Time Complexity

역으로 정렬되어 있을 경우가 최악의 경우이며

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2 이므로 O(N²) 이다

 

하지만 이미 정렬되어 있을 경우 한번씩 비교하여 O(N)의 시간복잡도를 가진다

---

Space Complexity

정렬하고자하는 배열안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다 (in-place sorting)

따라서 O(N) 이다

---

삽입 위치 설정 시 같은 값을 가지는 데이터를 만난경우 그 뒤에 삽입하기 때문에 stable sorting 이다