삽입 정렬 (Insertion sort)

1. 삽입 정렬 (insertion sort) 란?

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

두번째 데이터부터 시작해서 앞에 있는 것과 비교한다.

기준점과 앞으 데이터와 비교하면서, 삽입 안하고 비교만 하다가, 적절한 위치가 나오면 거기에 삽입한다.

 

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 

 

---

2. 어떻게 코드로 만들까? 

 

알고 가기

for index in range(10, 1, -1): # 10부터 시작해서 1 전 인 2까지 간다.
    print (index)

>>
10
9
8
7
6
5
4
3
2

 

수도 코드

for i in range(데이터길이 - 1): # 두번째 데이터를 기준으로 반복하므로
    for stand in range(i+1, 0, -1): # 첫번째 데이터까지 -1씩 이동한다.
        
        if data[stand] < data[stand-1]: # 기준데이터가 비교할 데이터보다 작을 때
            swap(data[stand], data[stand-1])
        
        else: # 기준데이터가 비교할 데이터보다 작지 않을 때
            break # 반복문 돌릴 이유 없으므로 멈춘다.

---

3. 알고리즘 구현

def insertion_sort(data):
    for i in range(len(data)-1):
        for stand in range(i+1, 0, -1):
            if data[stand] < data[stand-1]:
                data[stand], data[stand-1] = data[stand-1], data[stand]
            else:
                break
    return data

 

테스트

import random

data_list = random.sample(range(100), 50)
print (insertion_sort(data_list))

>> [1, 2, 3, 5, 8, 9, 10, 11, 14, 16, 17, 20, 22, 23, 32, 33, 34, 36, 40, 43, 46, 47, 49, 50, 51, 53, 56, 57, 60, 61, 62, 64, 65, 67, 68, 71, 72, 74, 75, 81, 82, 83, 85, 86, 89, 90, 91, 93, 96, 99]

---

4. 알고리즘 분석

반복문이 두 개 : O(𝑛^2)

• 최악의 경우, 𝑛∗(𝑛−1)/2

• 완전 정렬이 되어 있는 상태라면 최선은 O(n)

 

이해가 안 간다면? 코드보면서 이해하기

https://goo.gl/XKBXuk