Python 71 - 정렬 _ 기준에 따라 데이터를 정렬 (삽입 정렬)

삽입정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 그렇다면 다른 접근 방법에 대해서 생각해보자.

 

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?'

 

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 물론 삽입 정렬은 선택 정렬에 비해 구현 나니이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

 

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입' 한다는 의미에서 삽입 정렬(Insertion Sort)이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬 되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.

 

다음과 같이 초기 데이터가 구성되어 있다고 가정하자.

삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 떄문이다.

 

삽입 정렬은 재미있는 특징이 있는데, 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다. 그림을 보면 하늘색으로 칠해진 카드들은 어떤 단계든지 항상 정렬된 상태다. 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때 (삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 그림을 다시 살펴보자.

그림에서 '3' 은 한 칸씩 왼쪽으로 이동하다가 자신보다 작은 '0'을 만났을 때 그 위치에 삽입된다. 다시 말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그자리에 삽입되면 되는 것이다. 이제 소스코드를 확인해보도록 하자.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(1, 0, -1): #  인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j -1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break
        
print(array)

range의 세번째 매개변수

range의 매개변수는 3개 (start, end, step) 이다. 세번째 매개변수인 step에 -1이 들어가면 start 인덱스부터 시작해서 ㄷnd + 1인덱스까지 1씩 감소한다. 앞의 코드에서는 j변수가 i부터 1까지 1씩 감소한다.

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N²) 인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되 사용 되었다. 실제로 수행 시간을 테스트해보면 앞서 다루었던 선택 정렬과 흡사한 시간이 소요 되는 것을 알 수 있다. 여기서 꼭 기억할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우 O(N) 의 시간복잡도를 가진다. 바로 다음에 배울 퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효울적이나 정렬이 거의 되어있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

 

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding