Bubble 뒤쪽 확정
3
2
1
→
2
1
3
인접 비교로 큰 값을 오른쪽 끝에 보냅니다.
기초 정렬은 “어느 구간이 확정되는가”를 본다
세 알고리즘 모두 O(N^2)이지만, 비교하는 위치와 확정되는 구간이 다릅니다.
Selection 앞쪽 확정
4
1
3
→
1
4
3
남은 구간의 최솟값을 찾아 앞에 고정합니다.
Insertion 정렬 구간 확장
1
2
4
3
→
1
2
3
4
현재 key를 앞쪽 정렬 구간에 끼워 넣습니다.
거의 정렬?
이동이 적으면 삽입 정렬이 빠르게 끝납니다.
swap 흐름 추적?
버블 정렬은 비교와 교환 타이밍이 가장 잘 보입니다.
쓰기 비용 제한?
선택 정렬은 패스마다 최대 한 번만 교환합니다.
검증은 결과값만 보지 않습니다.
경계
안정성
빈 배열
중복
역순