삽입 정렬 삽입 위치
거의 정렬된 입력에서는 이동이 적어 빠르게 끝날 수 있습니다.
기초 정렬 비용
삽입 정렬, 조기 종료 버블 정렬, 선택 정렬은 모두 O(N^2)이지만 데이터 분포에 따른 차이가 큽니다.
인접한 두 값을 바꾸며 큰 값을 뒤로 보냅니다
한 패스에서 교환이 없으면 이미 정렬된 상태로 보고 멈춥니다.
선택 정렬 교환 단계
비교 횟수는 O(N^2)이지만 최소값을 찾은 뒤 한 번만 교환해 쓰기 횟수를 줄입니다.
정렬 입력별 약점
예제 배열을 직접 따라가면 불변식이 보입니다.
이동 비용
삽입 정렬은 한 칸씩 미는 연산이 성능을 좌우합니다.
교환 감지
버블 정렬의 swapped 플래그가 조기 종료를 만듭니다.
쓰기 횟수
선택 정렬은 매 반복 최대 한 번 교환합니다.