[알고리즘] 정렬 : 삽입정렬

삽입정렬은 원소가 자신의 자리를 찾고 해당 자리에 삽입되면서 정렬하는 기법이다. 숫자 카드를 손에 들고 있을 때 숫자들을 오름차순으로 정렬한다고 생각해보면 쉽게 연상할 수 있다.

---

개념

• 오름차순 기준으로 설명한다.
• N개의 원소가 있을 때 1번 인덱스의 원소부터 N-1번 인덱스의 원소까지 탐색을 진행한다.
• 현재 인덱스를 기준으로 이전 인덱스와 비교를 한다. 
• 만약 이전 인덱스가 더 크다면 현재 인덱스의 원소가 있어야하는 자리는 이전 인덱스이기 때문에 자리를 스왑한다.
• 스왑 후에도 이전 인덱스가 더 크다면 계속해서 자리를 스왑한다.
• 이 과정에서 이전 인덱스가 더 작거나 더 이상 비교할 원소가 없을 때는 비교를 종료한다.
• 위의 과정을 반복하면 정렬이 된다.

구현

• 10개의 숫자가 랜덤하게 나열되어 있다.
• for문을 통해 1번 인덱스부터 N-1번 인덱스까지 탐색을 진행한다.
• 만약 현재 인덱스가 이전 인덱스보다 작다면 자리를 바꿔주어야 한다.
• 이때 while문을 통해 계속해서 이전 인덱스보다 작을 때는 자리를 바꿔주도록 구현한다.

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

for i in range(1, N):
    if numbers[i] < numbers[i-1]:
        j = i
        # 더 이상 비교할 원소가 없거나 이전 인덱스보다 클 때 종료한다.
        while j > 0 and numbers[j-1] > numbers[j]:
            numbers[j-1], numbers[j] = numbers[j], numbers[j-1]
            j -= 1
            
print(*numbers)

 

특징

• 이미 많은 원소들이 정렬되어 있을 때 효과적인 정렬 기법이다.
• 그렇지 않거나 정렬해야 할 원소가 많을 때는 적합하지 않다.

시간 복잡도

역순 정렬과 같이 최악의 경우에는 계속해서 비교하면서 자리를 찾아야하기 때문에 O(N^2)의 시간 복잡도가 측정된다.