삽입 정렬(Insertion Sort)의 동작 원리와 성능 최적화
삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 배열을 나누어, 정렬되지 않은 부분의 요소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식의 알고리즘입니다.
1. 동작 원리와 루프 불변성
삽입 정렬의 핵심 아이디어는 루프 불변성(Loop Invariant)으로 설명할 수 있습니다. 길이 n인 배열 data에 대해, 인덱스 [0, i) 범위는 항상 정렬된 상태를 유지하며, 인덱스 ...
5월 29일 16:40에 게시됨