Algorithm - 삽입 정렬(Insertion Sort)

1. 삽입 정렬(Insertion Sort)

- 두번째 인덱스에 위치한 데이터를 기준으로 해당 데이터의 앞 쪽에 위치한 데이터와 비교하여 더 큰 값을 갖고 있다면 더 큰 값을 가진 데이터를 뒤로 밀어내는 방식이다. 삽입된 데이터보다 작은 데이터를 만날 때까지 반복한다. (아래 사진참고) 

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

 

 

 

1-A) 어떻게 구현할까?

ex) 5, 3, 2

 

[풀이]

1) 두번째 인덱스에 위치한 3을 기준으로 5와 비교한다. → 3, 5, 2

2) 2를 기준으로 5와 비교한다. → 3, 2, 5  → 자신보다 작은 데이터를 만나지 못해 다시 비교한다. 

3) 2를 기준으로 3과 비교한다. → 2, 3, 5  

4) 5를 기준으로 3과 비교한다. → 2, 3, 5  → 자신보다 작은 데이터를 만났으니 더 이상 비교할 데이터가 없다.

 

 

[규칙성]

1. n번째 턴에서는 n번 index가 기준 데이터가 된다. 

ex1) 첫번째 턴에서 로직을 적용할 데이터의 index는 1이다.(두번째 index) → 5,3,2 에서 3

ex2) 두번째 턴에서는 로직을 적용할 데이터의 index는 2이다.(세번째 index) → 5,3,2 에서 2

 

2. 기준 데이터보다 작은 값을 만날 때까지 비교 로직을 수행한다. 즉, 자신보다 작은 데이터를 만나면 로직을 멈춘다. 

 

 

[규칙성을 코드로 구현] 

#반복 횟수(턴) 
for index in range(len(data)-1): 

	# 기준 데이터의 index에서 이전 데이터를 비교
	# 0까지 설정하면 range는 1까지 연산(index-1 해야하기 때문에 1까지 설정) 
	for index2 in range(index+1, 0, -1): 
    	
        #기준 데이터의 위치(index2)와 그 앞에 위치한 데이터(index2 -1) 비교
    	if data[index2] < data[index2 - 1]:
        	swap(data[index], data[stand]
        else:
        	break #기준 데이터보다 작은 값을 만났다면 탈출 

 

 

 

1-B) 코드 구현 

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

 

 

 

[테스트 및 결과]

 

 

[참고자료]

https://goo.gl/XKBXuk

Live Programming Mode - Python Tutor - Visualize Python and JavaScript code

---

2. 선택정렬의 시간복잡도

- 버블정렬, 선택정렬과 동일하게 이중 for문을 사용하기 때문에 O(n^2)의 시간복잡도를 갖는다.

- 최악의 경우, {n(n-1)}/2의 시간복잡도를 갖는다.

- 최선의 경우, 완전 정렬이 되어있다면 O(n)의 시간복잡도를 갖는다.