[알고리즘/Algorithm] 파이썬으로 삽입 정렬(Insertion Sort) 알아보기

Insertion Sort (삽입 정렬)

: 다음과 같은 순서를 반복하며 정렬하는 알고리즘

1. 삽입 정렬은 두 번째 인덱스부터 시작
2. 해당 인덱스 앞에 있는 데이터(B)부터 비교해서 Key 값이 더 작으면, B값을 뒤 인덱스로 복사
3. 이를 Key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 Key 값을 이동

 

삽입 정렬 흐름

삽입 정렬은 그림과 같이 해당 인덱스의 요소에서 그 앞의 요소와 비교를 해서 앞의 요소가 크다면 서로 스왑을 해서

위치를 바꿔준다.

스왑을 한 번 해줬다고 바로 해당 인덱스의 다음 요소부터 또 비교를 시작하는 것이 아니라,

그림에서 4 ~ 6번과 같이 스왑된 요소가 자기 자리를 찾을 때까지 최대 0번째 인덱스까지 비교해서 자기 자리를 찾아간다.

위 그림에서는 생략돼 있지만 그림 6번 기준으로 숫자 1이 숫자 2의 자리까지 계속 비교 하면서 1이 2의 자리를 대신하게 될 것이다.

 

 

이것을 코드로 작성하면 아래와 같다.

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

안쪽 루프인 for문은 바깥 for문의 인덱스인 i를 기준으로 i + 1 부터 시작하여 0까지 -1씩 빼주며 계속하여 비교하면서 요소를 정렬해준다.

비교를 했지만 정렬이 돼 있으면 더이상 비교할 필요가 없으니 else문으로 break를 걸어줘 다음 요소를 비교하게 해줬다.

 

 

시간 복잡도

• 최악 : 역순으로 정렬돼 있으면 모든 for문이 반복돼서 시간 복잡도는 O(n^2)
• 최선 : 모두 정렬이 된 상태라면 바깥 루프 for문 한 번만 데이터를 확인하면 되기 때문에 시간 복잡도는 O(n)