삽입정렬 Insertion Sorting

기본적으로 ChatGPT를 이용하여 틀을 잡고 만든 것

정렬되지 않은 원소를 정렬된 부분집합에 삽입하는 방법으로 이미 정렬된 배열에 새로운 원소를 추가할 때 효율적으로 작동하는 알고리즘

삽입정렬 1

def insertion_sort(arr):
    # 모든 요소를 비교하기 위해 n-2번 반복
    for i in range(1, len(arr)):
        key = arr[i] # 삽입할 원소
        j = i - 1 # 정렬된 배열의 크기 + 삽입할 원소
        # j -> 0 범위로 줄여가면서 key값보다 작을 때까지 또는 j만큼 반복이 끝났을 때 종료
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[i]
            j -= 1
        arr[j+1] = key
    return arr

arr = [5, 2, 4, 6, 1, 3]
print(insertion_sort(arr))

[1, 1, 1, 1, 1, 3]

• 알고리즘
  • 첫번째 반복문
    • 모든 요소를 비교하기 위해 1~n 범위로 비교한다.
  • 두번쨰 반복문
    • 정렬된 배열의 크기 + 삽입할 원소의 크기만큼 반복
    • j -> 0 범위로 줄여가면서 key값보다 작을 떄까지 또는 j만큼 반복이 끝났을 때 종료
  • 마지막 Swap
    • 두번째 반복문이 끝나면 j+1 인덱스의 위치에 값이 들어갈 위치가 된다.
• 시간복잡도
  • 최선의 경우 O(N)으로 굉장히 빠른편에 속한다.
  • 최악의 경우 O(N^2)으로 굉장히 느려 최선의 경우와 차이가 많이 난다.
  • 정렬되어 있는 데이터라도 삽입순서에 따라 성능차이가 나므로 데이터의 상태가 성능의 주요요인이다.