[알고리즘] 파이썬으로 삽입 정렬(Insertion Sort) 구현하기

삽입정렬은 필요할 때만 적절한 위치에 삽입하는 알고리즘이다. 이것도 시간복잡도는 O(N**2)이나, 필요할 때만 수행하기 때문에 경우에 따라서는 굉장히 빨리 작동할 수도 있다. 따라서 앞서 설명했던 다른 알고리즘들(선택정렬, 버블정렬) 보다는 효율적이라고 할 수 있다. 

 

삽입정렬의 순서는 다음과 같다고 정리할 수 있다.

1. 주어진 리스트에서 비교할 값을 선정한다

2. 비교할 값을 이전까지의 값들과 '필요한 경우'에만 비교한다

 

주어진 숫자 리스트를 오름차순으로 정렬하라는 문제에 대하여 위 순서에 따라 코드로 구현해보면 다음과 같다.

# 필요할 때만, 적절한 위치에 삽입하여 정렬
def insertion_sort(array):
    for i in range(len(array)-1):
        j = i
        while (j>=0) and (array[j] > array[j+1]):
            temp = array[j]
            array[j] = array[j+1]
            array[j+1] = temp
            j -= 1
        print(array)
        
array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
insertion_sort(array)

이 알고리즘에서 생각해볼만한 문구는 '필요할 경우에만 비교'한다는 것이다. 일반적으로 어떤 조건에서만 돌아가게끔 하는 반복문은 while을 사용하면 구현이 가능하다는 점을 기억한다면, 앞서 다른 알고리즘에서 for문만 사용하다가 여기서 while문을 만나더라도 당황하지 않을 것이다.

 

(아래 링크는 파이썬 표준문서에서 이야기하는 while문에 대한 설명이니 필요한 사람만 참고)

 

https://docs.python.org/ko/3/tutorial/introduction.html#first-steps-towards-programming

 

다음은 위 코드를 구현했을 때, 정렬 작업의 출력 결과물이다. 상대적으로 이전의 알고리즘에 비해서는 적은 것을 확인할 수 있다.

 

참고 및 출처:

- 안경잡이 개발자, '4. 삽입정렬(Insertion Sort)' https://blog.naver.com/ndb796/221226806398

4. 삽입 정렬(Insertion Sort)