삽입정렬

삽입을 이용한 정렬 알고리즘

기존 정렬은
n개의 숫자를 주고 n개의 숫자를 정렬해야하는 문제인데
삽입 정렬은 n개의 숫자와 키 값을 주고 정렬을해야해서 문제를 조금 다듬을 필요가 있습니다.

주어진 문제 정확하게 푸는 알고리즘이 없을경우 문제를 변형해도 되는데 변형할때 시간이 알고리즘의 성능에 영향을 미치면 안된다.

$N$-1 번째는 $A[n]$을 정렬된 배열 $A[1..n-1]$에 집어넣는다.

선형함수

공간 복잡도

제자리 정렬이므로 공간을 사용하지 않는다

코드

numlist = [5, 3, 1, 4, 2]
j = 0
for i in range(1, len(numlist)):
    key = numlist[i]                    # 선택 정렬에 사용될 키
    j = i - 1                           # 정렬된 리스트의 길이 N-1
    while j >= 0 and numlist[j] > key:   # 인데스가 0보다 작지않고 정렬된 리스트 중 키값보다 작을경우에만
        numlist[j+1] = numlist[j]
        j = j-1
    numlist[j+1] = key

print(numlist)

정리

삽입정렬은 정렬된 배열또는 리스트와 키 값을 같이 주어지게 됩니다.
진행 방식은 정렬된 배열의 값과 키 값을 배열의 역순대로 키 값과 비교하며 키 값 보다 작은 값을 만나면 그에 해당하는 인덱스에 키 값을 삽입하게 됩니다.

코드로 표현하기 위해서는 주어진 배열을 정렬된 배열과 키 값으로 나눠줘야하기 때문에 첫 번째 인덱스과 두 번째 인덱스의 값을 가지고 있고
두 개의 값을 비교하여 두 번째 인덱스의 값이 첫 번째 항의 값보다 작다면 순서를 바꾼다. 이러한 점을 계속 인덱스를 늘려가며 키 값을 삽입하다 보면 배열을 정렬이 되기 됩니다.