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

1. 기본 원리

• 데이터를 왼쪽부터 오른쪽에 있는 값을 하나씩 추가하면서 확장해나간다. 
• 확장할 때마다 오른쪽에서 들어온 값들을 사이사이에 넣어보면서 정렬을 맞춰나간다.

ex)

a = [5,1,2,3]이면

1. [5,1] 범위에서 1을 5와 비교하여 [1,5]로 정렬

2. [1,5,2] 범위에서 2를 5,1과 비교하여 [1,2,5]로 정렬

3. [1,2,5,3] 범위에서 3을 5,2,1과 비교하여 [1,2,3,5]로 정렬

 

2. 코드 구현 전 생각정리

• 어느 범위까지 정렬 처리가 완료되었는지를 나타내는 좌표를 변수에 저장해야 하나?
• 왼쪽에서부터 점점 확장해나가는 범위? 는 이미 정렬이 되어있음을 명심

 

3. 코드 구현

def insertion(input):
    for i in range(len(input)-1):
        insert_idx = i+1
        for j in range(insert_idx,0,-1):
            if input[j]<input[j-1]:
                input[j-1],input[j] = input[j],input[j-1]
            else:
                break #이미 좌측은 정렬이 되어있기 때문에 왼쪽으로 이동하면서 수정이 필요한 부분이 보이지 않으면 break
   
    return input

 

 

4. 시간 복잡도

• 이중 for문이 있으므로 O(n^2)