[알고리즘] 삽입 정렬 (Insertion Sort) 이란? - 컴도리돌이

 

• 삽입 정렬(Insertion sort) 이란?

 

1. -삽입을 사용하면서 정렬하는 알고리즘으로 삽입할 값(key)과 값(key)들이 정렬된 리스트가 있을 경우, 정렬된 리스트에 값을 삽입할 때 정렬된 순서를 보존하면서 삽입을 하는 것이 삽입 정렬이다.
2. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

 

 

• 삽입 정렬(Insertion sort) 알고리즘 예제

 

---

  배열에 5,2,4,6,1,3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보았다.

 

1

 

 

 

2

 

key 2 와 첫 번째 자료인 5를 비교한다. 5가 2보다 더 크므로 5를 2자리에 넣고 2를 5의 자리인 첫 번째에 기억시킨다.

 

3

 

key 값 4랑 두 번째 자료인 5랑 비교한다. 5가 더 크므로 5를 세 번째 자리에 기억시킨다. 4와 첫 번째 자료인 2랑 비교를 한다. 2가 더 작으므로 4를 두 번째 자리에 기억시킨다.

 

4

5,6,7

 

---

 

• 삽입 정렬(Insertion sort) 수도코드 & C언어 코드

 

삽입 정렬(insertion sort) 수도코드

 

 

---

 

 

 

삽입 정렬(Insertion sort) c언어 코드

 

 

- 인덱스 0은 이미 정렬된 것으로 볼 수 있기 때문에 인덱스 1 값부터 비교를 시작한다.

- value = arr[i] 는 현재 삽입될 숫자인 i번째 정수를 value 변수로 복사하여 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다. j값을 음수가 아니어야 되고 value 값보다 정렬된 배열에 있는 값이 크면 j번째를 j-1번째로 이동한다.

 

 

 

• 삽입 정렬(Insertion sort) 알고리즘 시간복잡도

- 정렬 알고리즘은 대표적인 안정된 알고리즘이다.

1. best case : 비교 횟수가 이동 없이 1번의 비교만으로 이루어질 때 n-1번의 비교를 해준다. T(n) = O(n)
2. worst case : 각 반복마다 i번의 비교를 수행을 할 경우 O(n^2)가 걸리고, 각 단계마다 i+2번의 이동이 발생하기 때문에 O(n^2) 가 걸린다. T(n) = O(n^2)

- 삽입 정렬은 구현이 간단하지만 비효율적인 방법 중에 하나이다.

- 대부분의 값들이 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

- 입력 값이 많고 크기가 클 경우에 적합하지 않은 알고리즘이 된다.