[python]삽입 정렬

삽입 정렬(Insertion sort)이란?

---

앞에 요소를 살펴보고 그 값보다 작은 지 큰 지를 비교해 적당한 위치에 삽입해서 정렬하는 방법.

1. 리스트 중에 두 번째 요소를 key값으로 한다.
2. 그 앞에 값과 키값을 비교한 뒤 작으면 그 앞, 크면 그 뒤에 넣는다.
3. 그 다음 요소(세 번째)를 key값으로 한다.
4. 그 앞에 값(두번째 요소)와 키 값을 비교한 뒤 작으면 앞 크면 그 뒤에 넣는다.
5. 계속해서 반복한다.

직관적으로 이미지를 보면서 예를 들어보자면 다음과 같다.

(a)옆에 [3,7,2,5,1,4]라는 배열이 있다. 가장 앞에 값인 3을 제외하고 두 번째 값인 7을 키 값으로 설정한다. 빨간색 박스는 key값이라는 뜻이다. 이 key값인 7은 3과 비교해서 더 큰 값이므로 3 뒤에 위치하게 된다.

(b)다음으로 3번째 요소가 key값이 된다. key값인 2는 그 앞에 값인 7과 비교해서 더 작으므로 7의 앞에 위치하게 된다. 여기서 주의해야할 것은 단순히 7만 비교하는 것이 아닌 그 앞에있는 3과도 비교해서 최종적으로는 3의 앞에 위치하게 된다.

(c)부터는 마찬가지로 계속해서 key값을 기준으로 그 앞에 있는 값들과 비교해서 작으면 그 앞으로 크면 그 뒤에 위치 시킨다.

 

삽입 정렬 알고리즘의 특징

---

삽입,버블,선택 이 세 개중에서는 삽입정렬이 제일 뛰어나다. 앞에있는 요소들이 다 정렬이 되어있다는 가정하에 필요할 때만 위치를 바꾸는 정렬을 하기때문이다.

장점

• 요소가 적을 경우에 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 이미 정렬되어 있는 숫자가 많을 수록 다른 정렬에 비해 유리할 수 있다.

단점

• 반대로 요소가 많을 경우에는 적합하지 않다.

삽입 정렬의 시간복잡도

---

위에 장점에서 설명했떤 대로 삽입 정렬의 알고리즘의 특성상 이미 정렬이 끝난 리스트([1,2,3,4,5]같은..)를 넣어주면 단순히 O(n)으로 계산 복잡도를 마칠 수 있다.

하지만 이 경우는 최선의 경우이므로 일반적인 입력은 선택 정렬과 같은 O(n²)이다.

코드

---

#삽입 정렬
#리스트 a를 정렬함

def ins_sort(a):
    n = len(a) #리스트 a의 크기
    key = 0 #키 값 변수 선언
    for i in range(1, n): #첫번째 값부터 n-1까지 반복
        key = a[i] #키 값에 첫번째 값부터 마지막 값까지 들어감
        j = i - 1 #j는 비교해야하는 앞에 요소 첫번째의 경우 j는 0번째와 비교하게됨
        while j >=0 and a[j] > key: #key값보다 비교값이 클 때까지 안에 내용이 계속 반복
            #선택정렬과 달리 값을 삽입하는 것이므로 공간이 생기도록 값을 오른쪽으로 이동
            a[j + 1] = a[j] 
            j -= 1
        a[j + 1] = key #찾은 위치에 key를 넣는다
    return a
a = [5,3,2,4,1]
print(ins_sort(a))

while문에 들어있는 조건문이 핵심인데 만약 key값보다 앞에 있는 비교대상이 크면 그 비교대상의 값을 오른쪽으로 옮긴다. 이 부분이 햇갈릴 수가 있는데, 옮긴다기 보다는 덮어 씌우는 것이고 덮어 씌우는 과정에서 중복된 값이 들어갈 수 있으나 비교 값이 크면 바로 key값이 덮어 쓰인 곳에 들어가고 작다면 한번 더 검색해서 그 앞에 값이 다시 옮겨지기 때문에 계속해서 중복된 값이 쓰일 문제는 없다.

만약 리스트를 오름차순 정렬이 아니라 내림차순으로 정렬하기 위해서는 while문에 조건문인 a[j] > key 의 부등호를 반대로 a[j] < key 로 바꾸어주면 된다.