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

삽입 정렬(Insertion Sort)

---

삽입 정렬(Insertion Sort) 란?

삽입 정렬(Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입함으로써 정렬을 완성하는 알고리즘이다. 

 

삽입 정렬은 처음 Key 값을 두 번째 요소부터 시작하게 되며 그 앞쪽 요소들과 비교하여 삽입할 위치를 지정한 후 요소를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 

 

 

 

 

 

---

 삽입 정렬(Insertion Sort) 시간 복잡도

▶ 최악의 경우(입력 자료가 역순일 경우)

T(n) = O(n^2)

 

▶  최선의 경우(입력 자료가 정렬되어 있는 경우)

T(n) = O(n)

 

---

삽입 정렬(Insertion Sort) 알고리즘의 특징

1. 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다. 

2. 알고리즘 자체가 간단하며 안정 정렬(Stable Sort) 이다.

3. 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. 

     ✔ 제자리 정렬(in-place sorting)

4. 평균과 최악의 시간 복잡도가 O(n^2)로 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않으며 역순으로 정렬되어 있는 배열의 경우 비효율적이게 된다. 

 

---

삽입 정렬(Insertion Sort) 코드: Python

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x