[알고리즘][정렬] 삽입 정렬 - Insertion Sort

728x90

 

 

 

🙆‍♂️삽입 정렬

---

삽입 정렬은 앞에서부터 이미 정렬된 요소와 비교하여 자신의 위치에 삽입하는 정렬입니다.

 

 

🙋‍♂️방식

---

arr = [8,6,2,4]

이 배열을 오름차순으로 삽입정렬하려 하면

 

#level 1
arr = [6,8,2,4]

01. 8과 6을 비교하여 삽입

 

#level 2

#first
arr = [6,2,8,4]

#second
arr = [2,6,8,4]

02. 2와 8, 2와 6을 비교하면서 적절한 위치에 삽입

 

#level 3

#first
arr = [2,6,4,8]

#second
arr = [2,4,6,8]

03. 4와 8, 4와 6 4와 2를 비교해서 적절한 위치에 삽입

 

시간 복잡도는 O(n^2)입니다. 그리고 stable한 정렬입니다.

 

def select(arr):
    for i in range(1,len(arr)):
        tmp = arr[i]
        j = i-1
        while 0<= j and tmp < arr[j]:
            arr[j+1] = arr[j]
            j=j-1
        arr[j+1]=tmp
        print(arr)
    return arr

코드로 구현하면 이런 느낌 입니다.