[Algorithm] 삽입 정렬(Insertion Sort) .03

이번에 알아볼 알고리즘은 삽입 정렬(Insertion Sort)입니다.

원카드를 할 때를 생각해보면, 손 패의 카드를 숫자 순으로 정렬해서 손에 쥐고 있던적 있죠?

이 상태에서 카드를 뽑게 되면 순서에 맞춰 패에 카드를 넣게 되는데, 이 방식이 삽입정렬이라고 생각하면 좋아요!

 

2번째 원소 부터 시작하며,선택한 원소의 앞에 있는 원소들과 비교하여 삽입할 위치를 정한 뒤 원소를 뒤로 옮기고 지정된 자리에 원소를 삽입하는 정렬 알고리즘입니다.

 

🤔 과정 및 코드

먼저 2번째 위치의 값을 temp에 저장하고 해당 원소보다 아래 위치에 있는 값들과 비교하며 알맞는 위치에 삽입합니다.

이후 그 다음(3번째) 위치의 값을 temp에 저장하고 아래 위치에 있는 값들과 비교하며 삽입을 반복합니다.

 

📝 Python 예시 코드.

def insertionSort(arr):
    for index in range(1, len(arr)):
        temp = arr[index]
        prev = index - 1
        while (prev >= 0) and (arr[prev] > temp):
            arr[prev+1] = arr[prev]
            prev -= 1
        arr[prev+1] = temp
    return arr


print(insertionSort(arr))

🕒 시간 복잡도.

최악의 경우와 평균인 경우엔 반복문을 두 번 거치기 때문에  O(n^2)이 됩니다.

최선의 경우인 모두 정렬이 되어있는(Optimal)한 경우, 한번씩 밖에 비교를 안하는. 두번째 반복문인 while문은 if문처럼 비교만 하는 역할을 하게되어, 실질적으로 반복문은 한 번만 거칩니다. 따라서 O(n)의 시간복잡도를 가지게 됩니다. 

 

💾 공간 복잡도.

주어진 배열 안에서 움직이기 때문에  O(n) 입니다.

 

✋ 장점과 단점.

장점.

알고리즘이 단순하며, 대부분의 원소가 이미 정렬 되어 있는 경우에 매우 효율적일 수 있다.

배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (제자리정렬 - in-place sorting)

안정 정렬(Stable Sort) 이다. (기존의 순서가 어느정도 유지된다. 즉, 원카드를 할때 패에 있는 카드가 숫자 외 모양 순서가 하트 - 다이아 순이라면 정렬 후에도 하트 - 다이아로 유지된다.)

Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

 

단점.

평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.

 

 

 

참조.

GimunLee/tech-refrigerator