개념
- 데이터를 앞에서 하나씩 확인 후 특정 조건에 부합하는 위치(좌 or 우)에 삽입
- 왼쪽은 이미 정렬되어 있는 가정으로 접근
- 선택정렬에 비해 실행시간 측면으로 조금 효율적
- 처음 key값은 두번째(index 1)부터 시작
- 비교, 시프트(이동), 삽입등이 사용되는 알고리즘
순서(오름차순 기준)
- 1번 인덱스부터 시작하는 반복문을 만든다.
- 임시로 1번 인덱스값과 데이터를 가지고 ← 방향으로 반복 비교한다.
- 왼쪽은 이미 정렬되어 있다는 가정
- 왼쪽 값이 크다면 큰 값을 현재 position으로 변경해주고 position을 -1 해준다. (왼쪽 순회)
- 2, 3단계가 끝나면 현재 position에 임시 데이터 값을 저장한다.
특징
장점
- 알고리즘 코드가 간단해 레코드의 수가 적을때 사용
- 레코드가 거의 정렬되어 있을때 효율적
단점
- 많은 데이터의 이동 발생
- 데이터가 많고 크기가 클수록 효율성 떨어짐
예제 코드
|
|
시간복잡도
주어진 데이터의 원소 길이가 5일때 두수의 비교를 순차적으로 끝까지 하게 되면 총 4번의 횟수가 발생한다.
이때 끝까지 비교를 하면 4+3+2+1 = 10번이 발생한다. (n-1) + (n-2) ... + 1
시프트(이동) 또한 4+3+2+1 = 총 10번이 걸리게 된다.
최악의 경우 O(N^2) 시간복잡도를 가지게 되며, 이미 정렬되어 있는 최선의 경우 비교만 하고
이동이 필요하지 않기에 O(N)의 시간복잡도를 가진다.