[Algorithm] 삽입 정렬

※ 삽입 정렬이란?

 

아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식

 

 

 

다음 데이터 셋을 삽입 정렬로 정렬해보자.

 

 

[ 5, 1, 10, 8, 7, 6, 4, 3, 2, 9 ]

 

 

 

(1) 첫 번째 원소 5와 두 번째 원소 1을 비교했을 때, 더 작은 1을 5 앞으로 삽입한다. [1,5,10,8,7,6,4,3,2,9]

(2) 5를 1, 10과 비교했을 때, 5가 1보다 크고 10보다 작으므로 지금 상태를 유지한다. [1,5,10,8,7,6,4,3,2,9]

(3) 1, 5, 10은 정렬이 되어있으므로 8을 1, 5, 10과 비교했을 때, 1, 5보다 크고 10보다 작으므로 8을 10 앞에 삽입한다. [1, 5, 8, 10, 7, 6, 4, 3, 2, 9]

---

 

삽입 정렬을 파이썬으로 구현한 코드는 다음과 같다.

 

 

👩🏻‍💻Python Code👩🏻‍💻

 

data_set = [5,1,10,8,7,6,4,3,2,9]

for i in range(1,10):
    j = i
    while data_set[j]<data_set[j-1]:
        temp = data_set[j]
        data_set[j] = data_set[j-1]
        data_set[j-1] = temp
        if(i!=1):
            j -=1
        
print(data_set)

 

 

Explain ) 2번째 원소부터 왼쪽의 원소가 자신보다 작을 때까지 교체를 해준다. 이때, 해당 원소가 2번째 원소이면 한 번의 비교 후 정렬을 끝내고, 3번째 원소부터는 조건이 성립하지 않을 때까지 비교, 정렬을 진행한다.

 

 

삽입 정렬의 시간 복잡도는?

 

삽입 정렬은 최악의 경우 선택, 버블 정렬과 같이 O(N^2) 의 시간 복잡도를 가진다. 그러나 정렬을 진행하는 동안 왼쪽에 위치한 원소들은 정렬이 되어 있기 때문에 비교 연산을 덜 수행한다. 또한 어느 정도 정렬이 되어 있는 경우 선택, 버블 정렬보다 빠르게 정렬된다. 따라서 시간 복잡도는 동일하지만 실제로는 더 효율적인 정렬 알고리즘이다.