[Algorithm] 삽입 정렬 (Insertion Sort)

 

 

삽입 정렬 (Insertion Sort)

삽입 정렬은 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식으로 정렬하는 알고리즘.

 

 

 

작동 방식

• 인덱스 i에 있는 a를 정렬할 차례일 때, 인덱스 0부터 i-1까지는 이미 정렬된 상태
• 배열의 정렬된 부분에서 a보다 작거나 같은 수와 a보다 큰 수 사이에 a를 삽입한다.

예시

• 배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.

1. 5 3 8 1 2
2. 3 5 8 1 2
3. 3 5 8 1 2
4. 1 3 5 8 2
5. 1 2 3 5 8

시간 복잡도 : O(n^2)    * 1 + 2 + ... + (n-2) + (n-1) = n(n-1) / 2

 

 

 

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if arr[j-1] > arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
            else:
                break
    return arr