[Python] 삽입 정렬 (Insertion Sort)

각 숫자를 적절한 위치에 삽입시킨다.

다른 정렬 박식들은 무조건 위치를 바꾸는 방식이었다면 삽입정렬은 필요할 때만 위치를 바꾸게 된다.

 

 

 

 

파이썬 코드

# 삽입 정렬 (Insertion Sort)

def insertion_sort(arr):
    
    for i in range(len(arr)-1):
        # 현재 정렬할 원소를 선택해서 적절한 위치에 삽입할 수 있도록
        j = i 
        while arr[j] > arr[j + 1]:
            temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = temp
            j = j-1
            
    
    return arr
                
    
test = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
print("정렬된 데이터 : {}".format(insertion_sort(test)))

 

멈출 포인트를 알고있기 때문에 더 효율적이다.

데이터가 이미 거의 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다는 특징을 가진다.

 

 

 

 

 

시간복잡도

시간복잡도 O(N^2)으로 다른 정렬 알고리즘과 동일하지만 가장 빠르게 작동한다.

앞에 있는 숫자들이 정렬이 되어있다고 가정이 되어있기 때문에 불필요한 연산이 줄어들어서 빠름