Insertion Sort

# Insertion Sort

삽입정렬은 리스트의 앞에서 부터 이미 정렬된 서브 리스트의 값들과의 비교를 통해서 자신의 위치에 데이터를 삽입하는 방식으로 진행됩니다.

[ 우리는 정렬되지 않은 리스트를 정렬하고자하는 건데, 이미 정렬된 서브리스트는 어디서 나온것일까요? ]

만약 사이즈가 1인 배열이 있다면, 어떤 값이 들어 있어도 배열된 상태일 것입니다. 그래서 삽입정렬의 개념은 여기서 부터 시작됩니다.

리스트에서 가장 앞에 있는 하나의 원소를 이미 정렬된 서브리스트로 보고 정렬을 시작합니다. 그래서 실직적인 정렬 로직은 리스트의 두번째 원소, 즉 인덱스 1번의 위치부터 정렬을 시작하게 됩니다.

이미 정렬되어 있는 서브리스트 내에서 값 비교를 통해서 자신이 삽입되어야할 위치에 삽입이 됩니다

[ 정리 ] 

삽입정렬은 안정 정렬이며 버블정렬과 같이 알고리즘이 단순하다는 특징이있습니다. 또, 삽입 정렬은 데이터의 이동이 많기 때문에 리스트 내의 데이터가 어느정도 정렬되어 있는 상태일 경우에 데이터의 이동이 적어진다는 특징이 있습니다. 그래서 삽입정렬의 평균적인 시간복잡도는 O(N^2)이지만, 리스트가 모두 정렬되어 있는 최선의 경우 데이터를 이동시키는 로직을 실행하지 않아도 되기 때문에 시간복잡도는 O(N)까지 줄어들 수 있으며, 리스트가 역으로 정렬되어 있는 최악의 경우 모든 데이터에 대해서 로직이 이루어져야하기 때문에 O(N^2)의 시간복잡도를 갖게 됩니다.

 

 

# 코드 구현(Python)

def InsertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j>=0 and  arr[j]>key:
            arr[j+1] = arr[j]
            j = j-1
        arr[j+1] = key

for i in range(1, len(arr)):   가장 앞에 있는 원소(서브리스트)를 제외하고 순환합니다

    key = arr[i]                      key는 삽입위치를 찾아줄 데이터입니다

    j = i-1                               0부터 j는정렬된 서브리스트의 인덱스 입니다

    while j>=0 and  arr[j]>key: 
        arr[j+1] = arr[j]

 key값보다 정렬된 배열의 값이 클 때까지 데이터를 한칸씩 오른쪽으로 이동합니다. 근데 key값보다 정렬된 배열의 값이 작으면 더이상 값 이동할 필요가 없으므로 arr[j]>key를 while문 조건에 같이 걸어줍니다
        j = j-1                        j부터 0까지 역순으로 서브리스트 순환

    arr[j+1] = key              while문이 끝난 자리에 key값 삽입

 

[ Test Code ] 

if __name__ == '__main__':
    arr = [9,1,6,3,7,2,8,4,5,0]
    InsertionSort(arr)
    print(arr)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

# 전체 코드

깃허브에서 테스트 코드를 포함한 전체 코드를 보실 수 있습니다.

GitHub - sonzwon/TIL: Today I Learned