파이썬 삽입정렬 알고리즘 Insertionsort #8

파이썬 삽입정렬 알고리즘 Insertionsort #8

 

안녕하세요. 파이썬으로 배우는 알고리즘~ 삽입 정렬입니다.

 

이번 시간의 삽입 정렬은 지난번 했던 순차 탐색과 거의 비슷합니다.

 

 

https://stricky.tistory.com/171

[파이썬_알고리즘] 순차 탐색 sequential search #7

하지만 문제를 푸는 방법이 조금 다르다고 할까요? 

 

7개의 숫자가 있습니다. 첫 번째 숫자부터 하나씩 꺼내서 다른 리스트에 삽입하면서 정렬을 합니다. 다만 나중에 들어오는 숫자는 기존에 들어와 있던 숫자와 큰지 작은지 비교하여 자기 자리를 찾아 작은 숫자부터 큰 숫자 순서로 들어가게 하는 게 삽입 정렬입니다.

 

그렇게 한 리스트에 있는 모든 숫자를 다른 리스트로 삽입하면서 정렬을 하는 겁니다.

 

매우 간단하지 않나요?

 

그림으로 한번 볼까요?

위에 있는 그림과 같은 순서로 연산이 이루어지게 됩니다.

 

아래 리스트에 있는 숫자들을 위의 리스트에 정렬하여 삽입합니다.

 

파이썬 코드로 표현하면 어떻게 될까요?

# 쉽게 설명한 삽입 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트

# 리스트 r에서 v가 들어가야 할 위치를 돌려주는 함수
def find_ins_idx(r, v):
    # 이미 정렬된 리스트 r의 자료를 앞에서부터 차례로 확인하여
    for i in range(0, len(r)):
        # v 값보다 i번 위치에 있는 자료 값이 크면
        # v가 그 값 바로 앞에 놓여야 정렬 순서가 유지됨
        if v < r[i]:
            return i
    # 적절한 위치를 못 찾았을 때는
    # v가 r의 모든 자료보다 크다는 뜻이므로 맨 뒤에 삽입
    return len(r)

def ins_sort(a):
    result = []  # 새 리스트를 만들어 정렬된 값을 저장
    while a:     # 기존 리스트에 값이 남아 있는 동안 반복
        value = a.pop(0) # 기존 리스트에서 한 개를 꺼냄
        ins_idx = find_ins_idx(result, value)  # 꺼낸 값이 들어갈 적당한 위치 찾기
        result.insert(ins_idx, value)  # 찾은 위치에 값 삽입(이후 값은 한 칸씩 밀려남)
    return result

d = [2, 4, 9, 7, 5, 8, 3]
print(ins_sort(d))

그렇다면 다른 방법은 없을까요?

 

새로운 배열에 넣는 방식 말고, 자기 배열에서 자리를 바꾸어 정렬하는 방법도 파이썬 코드로 표현해 보겠습니다.

# 삽입 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)

def ins_sort(a):
    n = len(a)
    for i in range(1, n):  # 1부터 n-1까지
        # i번 위치의 값을 key로 저장
        key = a[i]
        # j를 i 바로 왼쪽 위치로 저장
        j = i - 1
        # 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]  # 삽입할 공간이 생기도록 값을 오른쪽으로 한 칸 이동
            j -= 1
        a[j + 1] = key  # 찾은 삽입 위치에 key를 저장

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)

조금 더 간단하게 코드가 표현되는 것 같습니다.

 

마지막으로 이 알고리즘에 대한 분석을 해보겠습니다.

 

삽입 정렬 알고리즘의 계산 복잡도 역시 이전의 순차 탐색처럼 어떤 변수가 리스트에 어떻게 들어가 있느냐에 따라 많이 달라질 수 있습니다.

 

하지만 계산 복잡도는 가장 보수적으로 계산을 해보아야 하는데요, 일반적으로 입력되는 변수가 정렬되지 않은 상태로 있을 때 보통 O(n2)의 계산 복잡도를 가집니다. 하나의 변수(n)를 처리하는데 비교 연산을 계속해야 한다는 점 때문입니다.

 

다음 이 시간에는 병합 정렬에 관해 살펴보겠습니다.

 

감사합니다.

 

 

by.sTricky