삽입 정렬은 리스트의 길이를 하나씩 늘리면서 맨 끝의 원소가 제 자리를 찾을 수 있게 비교하여 정렬하는 알고리즘이다.
- 삽입 정렬의 특징
- O(N^2)
- 이미 정렬되어 있는 리스트의 경우, 원소의 위치를 바꾸지 않아도 되므로 O(N)
- 리스트의 길이가 2일 때부터 한 번의 과정을 통해 하나의 원소의 위치를 결정함으로써 원소들의 위치를 순서대로 정해주므로 매 과정마다 리스트의 정렬에 대한 정확도를 보장한다.
Insertion Sort
Apr 29, 2019