삽입 정렬
IT 위키
- Insertion Sort
- 정렬된 앞부분에 다음 원소를 알맞은 자리에 끼워 넣어 가며 정렬하는 방법
카드를 손에 쥐고 한 장씩 제자리에 꽂아 넣는 것과 같다.
- 두 번째 원소부터 시작한다. 그 앞은 이미 정렬된 구간으로 본다.
- 꺼낸 원소를 정렬된 구간의 원소들과 뒤에서부터 비교한다.
- 꺼낸 원소보다 큰 원소는 한 칸씩 뒤로 밀고, 자리가 나면 끼워 넣는다.
- 마지막 원소까지 반복한다.
예 : 50 80 20 → 50 80 20 → 50 20 80 → 20 50 80
- 평균·최악 : O(n²). 역순으로 정렬된 자료가 최악이다
- 최선 : O(n). 이미 정렬돼 있으면 비교만 n−1 번 하고 이동이 없다
- 공간 : O(1). 배열 안에서 자리를 바꾸는 제자리 정렬이다
- 안정 정렬이다. 값이 같은 원소의 순서가 뒤바뀌지 않는다.
- 거의 정렬된 자료에 매우 빠르다. 이 성질 때문에 퀵 정렬이나 머지 소트가 작은 구간에 이르면 삽입 정렬로 넘기는 구현이 많다.
- 자료가 적을 때는 단순함 덕분에 오히려 빠르다.
- 자료가 많고 무작위면 O(n²) 이라 쓰기 어렵다.
