[Python] 이것이 코딩테스트다 with 파이썬 - 정렬 - 삽입 정렬

들어가기 앞서

 

해당 문제 및 해설은 "이것이 코딩 테스트다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다. 

 

 

챕터 순서

 

1. 선택 정렬 알고리즘

2. 삽입 정렬 알고리즘

3. 퀵 정렬 알고리즘

4. 계수 정렬 알고리즘

 

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

---

정렬 알고리즘

 

정렬 이란, 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다.
알고리즘 효율성을 쉽게 이해할 수 있는 정렬을 통하여 코딩 테스트 합격률을 높여보도록 한다. 
정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 정리 해보려고 한다.

 

삽입 정렬 알고리즘

 

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까? '

삽입 정렬은 선택정렬에 비해 구현 난이도가 높은 편이지만, 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다.

특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다.

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입' 한다는 의미에서 삽입 정렬 이라고 부른다.

 

• 삽입 정렬은 두 번째 데이터부터 시작한다.
• 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

 

---

 

삽입 정렬 그림 설명

 

 단계 0  첫 번째 데이터 '7' 은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5' 가 어떤 위치로 들어갈지 판단한다. '7' 의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 우리는 카드를 오름차순으로 정렬하고자 하므로 '7' 의 왼쪽에 삽입한다.

 

  

 단계 1  이어서 '9' 가 어떤 위치에 들어갈지 판단한다. 삽입 될 수 있는 위치는 총 3 가지 이며, 현재 '9' 는 '5' 와 '7' 보다 크기 때문에 원래 자리 그대로 둔다.

 

 

 단계 2  이어서 '0' 이 어떤 위치에 들어갈지 판단한다. '0' 은 '5', '7', '9' 와 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입한다.

 

  

- - 중략 - - 

 

 단계 8 

 

 

 단계 9  이와 같이 적절한 위치에 삽입하는 과정을 N - 1 번 반복하게 되면 다음과 같이 모든 데이터가 정렬 된 것을 확인할 수 있다.

 

 

소스 코드 

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
	for j in range(i, 0, -1) : # 인덱스 i부터 1까지 감소하며 반복하는 문법
    	if array[j] < array[j - 1] : # 한 칸씩 왼쪽으로 이동
        	array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈충
        	break
    
print(array)
 
# 출력
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

삽입 정렬의 시간 복잡도

 

삽입 정렬의 시간 복잡도는 O(N^2) 이다.

삽입 정렬에서의 기억해야 할 점은, 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면, 매우 빠르게 동작한다는 점이다.

최선의 경우에는 O(N) 의 시간 복잡도를 가진다.

 

결론적으로, 거의 정렬 되어 있는 상태로 입력이 주어지는 문제라면, 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것 보다,
삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.