Insertion
1
2
4
3
→
1
2
3
4
삽입 위치까지 값만 밀어낸다
거의 정렬된 입력에서는 이동 수가 작아 최선 O(N)이 됩니다.
삽입, 버블, 선택은 같은 차수라도 줄이는 비용이 다르다
이동, 교환 감지, 쓰기 횟수를 나눠 보면 적용 범위가 보입니다.
Bubble
3
2
1
→
2
1
3
인접한 두 값을 바꾸며 큰 값을 뒤로 보낸다
한 패스에서 교환이 없으면 swapped=false로 바로 멈춥니다.
Selection
8
4
2
6
→
2
4
8
6
최솟값을 찾은 뒤 한 번만 교환한다
비교는 많지만 쓰기 횟수는 패스마다 최대 한 번입니다.
거의 정렬
삽입 정렬
흐름 추적
버블 정렬
쓰기 제한
선택 정렬
큰 데이터
내장 정렬