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

공부한 날짜: 2021. 10. 21 

 

삽입정렬

: 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 적당한 곳에 삽입해 나가는 알고리즘. 

 

구현방법

1. 데이터 집합에서 정렬 대상이 되는 요소를 선택한다. 정렬 대상 범위는 최소 2부터 최대 '데이터 집합의 크기 -1'이다. 하나씩 늘려나감.

2. 가장 오른쪽 요소가 가장 크지 않다면 뽑아내서 적절한 곳(데이터 집합 가장 왼쪽을 기준으로 했을 때 자신보다 더 작은 요소가 없는 위치)을 정렬 대상 내에서 찾는다. 

3. 적절한 곳을 찾았다면, 삽입할 값보다 큰 값을 가진 요소들 한자리씩 오른쪽으로 이동시키고, 새로 생긴 빈자리에 삽입시킨다.

4. 전체 데이터 집합이 완료될 때가지 1~3을 반복한다.

 

-버블정렬과 달리 삽입 정렬은 정렬 대상을 하나씩 늘려나가는 방식으로 진행된다. 

-삽입 정렬의 비교 횟수 범위(데이터 개수 n개일 때) : 최소 (n-1), 최대 n(n-1)/2