삽입 정렬 (Insertion Sort) 알고리즘

오늘은 비교정렬 알고리즘인 삽입 정렬 (Insertion Sort) 알고리즘에 대해 알아보겠습니다!

 

# 동작과정 

삽입정렬은 이름과 같이 매번 적절한 위치에 해당 값을 삽입하는 알고리즘입니다!

간단한 예시로 트럼프 카드 게임을 생각하면 되는데욥! 

1. 카드를 뽑고 2. 위치를 찾고 3. 삽입 하는 과정을 생각하면 됩니다!! 

 

아래는 5,3,4,1,2 다섯개의 숫자를 정렬하는 예시인데욥

동그라미 숫자는 동그라미 왼쪽의 정렬된 값에서 매번 삽입될 위치를 찾는 식으로 동작합니다!

 

# Python 코드

def insertion_sort(A):

    n = len(A)

    for i in range(1,n):

        key = A[i] # 삽입할 요소

        j = i-1  # 삽입할 요소 보다 왼쪽에 위치한 인덱스들 비교

        # arr[0...i-1] 범위에서 key(삽입할 요소)보다 큰 요소들을 한 칸씩 오른쪽으로 이동

        while j>=0 and A[j] > key:

            A[j+1] = A[j]

            j-=1

        A[j+1] = key # 삽입할 값을 적절한 위치에 삽입

    return A

 

# 성능분석 - 시간복잡도

삽입정렬의 시간복잡도는 3가지 종류가 있는데욥 1. 최선인 경우(Best)  2. 최악의 경우(Worst) 3. 평균적인 경우(Average)  가 있습니다

 

1. 최선인 경우(Best) = O(𝑛)
2. 최악의 경우(Worst) = O(𝑛^𝟐)
3. 평균적인 경우(Average) = O( 𝑛^𝟐 )

 

1. 최선인 경우(Best) = O(𝑛)

최선의 경우는 이미 정렬되어 있는 경우입니다

총 n-1번의 비교만으로 정렬이 이루어 지는데요

즉,O(𝑛)의 시간복잡도를 보입니다

 

2. 최악의 경우(Worst) = O(𝑛^𝟐)

최악의 경우에는 정렬의 목적과 반대로 정렬되어 있는경우를 의미합니다!

각 값은 n-1번의 비교를 통해 정렬이 이루어지게 되며 이를 등차수열의 합으로 표현할 수 있습니다.

이를 모두 더하면 O(𝑛^𝟐)의 시간복잡도를 보입니다

최악의 경우 이동(교환)횟수는 (n-1)n / 2 + 2(n-1)   = O(n^2)입니다

(n-1)n / 2 -> 비교시 각 요소 이동

2(n-1)  -> (정렬된 부분 오른쪽으로 한칸 이동 + 삽입하는 요소 이동) X  총 n-1번 = 2(n-1) 

 

3. 평균적인 경우(Average) = O( 𝑛^𝟐 )

1) i번째 원소 삽입 시, 평균 비교횟수

2) 총 비교의 합

 

2가지 과정을 통해 평균적인 경우를 계산할 수 있는데요

여기서 summation을 적분으로 근사하여 계산할 수 있습니다!

 

삽입정렬은 평균적인 경우에만 봤을 때, 매우 비효율적인 정렬방식인데요
최선인 경우(Best) O(𝑛)의 시간복잡도를 가진다는 것을 고려하여 다른 정렬들과 결합한다면 좋은 성능을 낼 수 있습니다!

 

예) 1000만의 기존 정렬된 값 + 신규 유입된 10만 =>정렬 

-> 신규 유입된 10만의 값은 성능이 좋은 다른 정렬(Heap sort 등)을 이용한 후, 기존의 정렬된 값에 삽입시 삽입정렬(Insertion sort)를 이용한다면 이 경우에는 O(𝑛)의 시간복잡도만으로 정렬할 수 있습니다!

 

# 관련 문제

백준 11399번 - ATM

https://www.acmicpc.net/problem/11399

 

 

# reference

컴퓨터 알고리즘. (2006). 대한민국: 도서출판 홍릉(홍릉과학출판사).

Baase, S., Van Gelder, A. (1999). Computer Algorithms: Introduction to Design and Analysis, 3rd Edition. 인도: Addison-Wesley.

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))