[Python 자료구조] 단순 삽입 정렬 ( straight insertion sort )

💡 Straight InSertion Sort ( 단순 삽입 정렬 )

단순 삽입 정렬은 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다.

선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 것이 다르다.

 

삽입이라는 말 그대로, 들어서 자기 자리에 꽂아주는 것이다.

 

💡 설명

[그림 1]

두 번째 원소인 4 부터 주목하여 진행한다.

4는 6보다 앞쪽에 위치해야 하므로 맨 앞에 삽입한다.

이 상태에서 6을 우측으로 옮기면 [그림1] 의 두 번째 처럼 4, 6, 1 ... 8 이 나오게 된다. 

 

다음으로 세 번째 원소인 1에 주목하여 진행한다.

1은 4보다 앞쪽에 위치해야 하므로 맨 앞에 삽입한다.

이 상태에서 4와 6을 우측으로 옮기면 [그림1] 의 세 번째 처럼 1, 4, 6 ... 8 이 나오게 된다.

 

그 이후에도 계속 같은 작업을 반복하여

아직 정렬되지 않은 부분을 n - 1 번 반복하여 정렬한다.

아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입한다.

 

 

💡 다른 숫자로 설명 

3, 6, 2, 5, 4, 1 의 숫자가 있는 경우 아래와 같은 방법으로 진행된다.

3 6 2 5 4 1
2 3 6 5 4 1
2 3 5 6 4 1
2 3 4 5 6 1
1 2 3 4 5 6

 

💡 코드

def insert_sort(arr):
    size = len(arr)

    for i in range(1, size):

        j = i - 1
        key = arr[i]
        
        while arr[j] > key and j >= 0:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr
 
arr = [31, 25, 12, 22, 11]
 
print(insert_sort(arr))

 

블로그 수정 시 참고 하려는 글 : https://the-nest-of-cskim.tistory.com/11

 

💡 참고

반응형

 

Key: 25
before [31, 25, 12, 22, 11]
aftre [25, 31, 12, 22, 11]

Key: 12
before [25, 31, 12, 22, 11]
aftre [12, 25, 31, 22, 11]

Key: 22
before [12, 25, 31, 22, 11]
aftre [12, 22, 25, 31, 11]

Key: 11
before [12, 22, 25, 31, 11]
aftre [11, 12, 22, 25, 31]

[11, 12, 22, 25, 31]