[알고리즘/Python] 삽입정렬 | Insertion sort

 삽입정렬 [ Insertion sort ]

 

- 배열의 인덱스를 늘려가면서 원소가 들어가야할 자리를 찾아서 삽입하는 정렬

 

       -정렬 완료 된 부분      - 자리를 찾아야하는 원소

1	[34, 24, 67, 43, 93]
2	[24, 34, 67, 43, 93]
3	[24, 34, 67, 43, 93]
4	[24, 34, 43, 67, 93]

 

시간복잡도 ⏱

•     최선의 경우 : O(n) 
  • 이미 정렬이 다 되어있는 경우

•     최악의 경우 :  O(n²)   
•     평균 :  O(n²)

장점

 

1. 거의 정렬되어 있는 상태 ( O(n) ) 면 매우 빠른 효율성을 가지고 잇다

 

단점

 

1. 최악의 경우 ( ex : 거꾸로 정렬되어 있는 경우 ) O(n²) 라는 시간복잡도를 갖게 된다.

2. 데이터의 상태와 크기에 따라성능의 편차가 심하다

 

[ python insertion sort code | 파이썬 삽입 정렬 코드 ]

data = list(map(int, input().split()))

def insert_sort(data):

    for i in range(1,len(data)):
        tmp = i
        while data[tmp] < data[tmp-1] and tmp > 0:
            data[tmp],data[tmp-1] =  data[tmp-1],data[tmp]
            tmp -= 1

insert_sort(data)
print(data)

 

---

[ 합병정렬 | Merge Sort ]

[ 힙 정렬 | Heap Sort ]

[ 선택 정렬 | Selection Sort ]

[ 퀵 정렬 | Quick Sort ]