알고리즘/정렬
[알고리즘] 삽입 정렬(Insertion Sort)
chanmyung
2018. 4. 30. 12:22
삽입 정렬(Insertion Sort)
설명
오름차순의 경우
K번째 원소를 이전 원소와 비교하며 이전 원소가 K번째 원소보다 작을 때 까지 이전 원소를 다음 인덱스의 값으로 이동시킨다.
그 후 그 자리에 K번째 원소를 끼워 넣는다.
동작
동작 예시
정수형 배열이 [5, 3, 2, 4, 1] 5개의 원소를 가질 때 오름차순 정렬
인덱스는 1부터 시작 (이전 원소와 비교해야 하는데 0은 이전 원소가 없다.)
- 3과 5 비교, 밀어내기 O
[5,5, 2, 4, 1] - 3을 0번지에 끼워 넣음
[3, 5, 2, 4, 1] - 2와 5 비교, 밀어내기 O
[3, 5,5, 4, 1] - 2와 3 비교, 밀어내기 O
[3,3, 5, 4, 1] - 2를 0번지에 끼워 넣음
[2, 3, 5, 4, 1]
이를 반복
시간 복잡도
O(n^2)