삽입 정렬

삽입 정렬 (Insertion Sort)

💡 삽입 정렬(Insertion Sort)은 카드를 정렬하는 방법에 비유될 수 있는 정렬 알고리즘입니다. 이 알고리즘은 각 숫자를 적절한 위치에 "삽입"함으로써 작동합니다.

 

작동 원리

http://algorithm.wiki/ko/app/

1. 두 번째 원소부터 시작하여 현재 원소를 "임시 변수"에 저장한다.
2. 이전 원소들과 비교하면서 적절한 위치를 찾아간다.
   • 현재 원소가 이전 원소보다 작으면, 이전 원소를 한 칸 뒤로 이동한다.
3. 임시 변수에 저장한 원소를 적절한 위치에 삽입한다.
4. 위의 과정을 배열의 마지막 원소까지 반복한다.

시간 복잡도

• 최선의 경우: O(n) (이미 정렬된 배열에서)
• 평균적인 경우: O(n2)
• 최악의 경우: O(n2)

공간 복잡도

• O(1) (in-place 정렬)

장단점

• 장점:
  • 구현이 비교적 간단하다.
  • 데이터의 양이 작거나 이미 부분적으로 정렬되어 있는 경우 효율적이다.
  • 공간 복잡도가 작다.
• 단점:
  • 데이터의 양이 많아지면 시간 복잡도가 크므로 비효율적이다.

 

구현

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