[알고리즘] 삽입 정렬 (w/파이썬)

---

개념

타겟인 데이터의 앞 데이터들의 크기를 따져서

본인보다 큰 데이터 앞, 작은 데이터 뒤에 데이터를 삽입하는 방법이다.

 

이 배열을 삽입정렬로 오름차순 정렬해보자.

 

1. 처음은 처음의 다음 인덱스부터 타겟을 잡고 앞과 비교한다.

0번 인덱스의 데이터가 1번보다 크다. 그리고 0이 첫번째이기 때문에 더이상 앞으로 가 비교 할 데이터가 없다.

 

 

2. 2번 인덱스를 타겟으로 잡고 0, 1인덱스와 비교한다.

 

8을 보니 2보다 크기 때문에 교환 대상이지만,

삽입 정렬은 버블 정렬처럼 교환하지 않는다.

'삽입' 하기 때문에 우선 2를 빼 두고 8을 2자리로 옮긴다.

0번째 데이터도 있기 때문에 2와 또 비교해본다.

3이 2보다 크기 때문에 3도 밀고 그 자리에 2를 '삽입' 한다.

 

3. 3번 인덱스를 타겟으로 잡고 0, 1, 2와 비교한다.

비교 해 봤을 떄, 인덱스 3보다 큰 수는 인덱스 2이기 때문에 아래와 같이 적용한다.

 

4. 마지막 4번 인덱스를 타겟으로 잡고 0, 1, 2, 3번 인덱스를 비교하자.

2번 3번 인덱스가 타겟 인덱스보다 크므로 아래와 같이 처리한다.

끝

---

구현

그림은 일단 빼 두고 다 밀어둔 후 삽입하는 것 처럼 보이지만,

실제 구현은 그냥 교환으로 구현할 수 있다.

 

lists = [8, 3, 2, 7, 6]

for i in range(1, len(lists)):
    for j in range(i, 0, -1):
        if lists[j - 1] > lists[j]:
            lists[j - 1], lists[j] = lists[j], lists[j - 1]
print(lists)

 

그렇지만 이 구현 방법 또한,

이미 정렬이 된 리스트나, 이미 부분적으로 정렬이 된 부분을 불필요하게 도는 경향이 있다.

이미 정렬이 다 된 리스트라면 O(n)으로도 충분히 구현할 수 있는데

불필요하게 O(n^2)로 시간복잡도를 나타내야 하는 것이다.

 

그렇기에 새로 추가된 값 보다 작은 수가 나올 때 까지만 루프를 돌면 더이상 불필요하게 돌지 않아도 된다.

 

이를 최적화 하기 위해 아래와 같이 구현한다.

 

lists = [8, 3, 2, 7, 6]

for i in range(1, len(lists)):
    j = i
    # 이전의 수 보다 타겟이 작아지는 것이 한 번 이라도 나타날 대 까지 루프
    while j > 0 and lists[j - 1] > lists[j]:
        lists[j - 1], lists[j] = lists[j], lists[j - 1]
        j -= 1
print(lists)

---

시간복잡도

보통은 O(n^2)

올 정렬 된 리스트라면 O(n)