삽입정렬

삽입정렬

삽입정렬은 앞선 버블정렬과 선택정렬에 비해 시간복잡도가 우수하다. 삽입정렬에서의
핵심은 이중 for문을 사용하지만 특정 조건에 부합하지 않으면 코드를 멈추고 순회하
는 것에있다. 해당 말이 무슨 의미인지 한 번 살펴보기로 하자.

def insertion_sort(array):
    n = len(array)
    a = n - 1
    p = n - 1
    for i in range(n - 1):
        p -= 1
        for j in range(a - p, 0, -1):
            if array[j] < array[j-1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break
    return array

다음은 삽입정렬의 코드이다. 삽입정렬의 for문의 index의 양태가 어떻게 되는지 파악
하는 것이 삽입정렬을 이해하는데 좋다.

i = 0일 때 j = 1
i = 1일 때 j = 2 -> 1
i = 2일 때 j = 3 -> 2 -> 1

.
. 
.

i = len(array) -1일 때 j = len(array) -2 . . . -> 1

순으로 index가 진행이 된다. [5, 4, 3, 2, 1] 배열이 있을 때 이중 for문을 통해 5와
4를 비교한다. 내림차순으로 정렬되어 있을 경우 오름차순으로 순번을 변경한다. 그러니까
한번의 사이클이 돌면 [5, 4, 3, 2, 1]은 한번의 사이클이 돌면 [4, 5, 3, 2, 1]로 변
경된다.

이제 i=1이 되고 j=2부터 1순으로 거꾸로 순회가 시작된다. 내림차순으로 되어 있을 때 변
경이 발생하고 그렇지 않을 경우 그 차례때 break 하여 다음 턴으로 넘어가는 식으로 코드
를 짰기 때문에 시간복잡도가 앞선 버블정렬과 선택정렬보다 효율적이다. 이처럼 break를 할
수 있는 이유는 j이전의 elem들이 모두 오름차순으로 정렬이되어 있기 때문이다.

따라서 새로 추가된 j의 index에 해당하는 elem이 등장했을 때 해당 elem과 그전의 원소의
대소비교만 수행해서 내림차순에 해당 할 때에만 코드가 실행되고 더이상 내림차순이 실행되
지 않기 때문에 특정원소가 특정 자리를 찾아서 들어간다는 모양새 이므로 삽입정렬이라고 생
각 할 수 있다.

직접 코드를 구현하면서 느꼈던 것은 이중 for문의 index가 일반적이 형태가 아니기 때문에 
이 부분을 어떻게 짤지 생각해서 구성하는 것이 삽입정렬의 구현에 있어 핵심이 될 것 같다.