삽입정렬(Insertion Sort)

말그대로 삽입 즉, 꽂아 넣는 정렬입니다.

• 자신보다 앞의 원소가 큰지 작은지 비교해, 자신의 위치를 찾아 삽입 하는 정렬입니다.

• 이미 정렬이 되어있는데

• 삽입을 하면할 수록, 데이터가 하나씩 밀리기 때문에 효율이 떨어집니다.

• 시간 복잡도: O(n**2)

• 데이터가 이미 정렬되어 있다면 O(n)이다. 그러나, 데이터가 역순으로 정렬된 상태라면 삽입을 위해 값을 하나씩 뒤로 밀어내는 과정을 아주 많이 반복해야 하므로 느리다.

http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html

def insertionSort(arr):
    if len(arr)<2:
        return arr
    for i in range(1,len(arr)):
        val = arr[i]
        while i>0 and x[i-1] > val:
            arr[i] = arr[i-1]
            i-=1
        arr[i] = val

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

참고 문헌

https://blockdmask.tistory.com/98
http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html