불변식 찾기
각 반복이 끝난 뒤 어느 구간이 정렬되거나 위치가 확정되는지 적는다.
불변식이 loop 범위를 결정한다비교 범위 확인
이미 확정된 구간을 다시 비교하지 않도록 inner loop 끝을 줄인다.
off-by-one은 마지막 두 원소에서 드러난다교환 조건 보기
같은 값일 때 교환하는지 여부가 stable 성질을 바꾼다.
<와 <= 차이를 실제 중복 입력으로 본다입력 분포 테스트
이미 정렬, 역순, 중복 많음, 원소 0/1개 입력에서 비교 횟수와 결과를 본다.
최선/최악 시간은 입력 모양에 달려 있다출력 검증
정렬 여부뿐 아니라 원소 개수 보존과 중복 순서 보존이 필요한지 확인한다.
값만 맞아도 안정성이 깨질 수 있다Bubble
인접 교환
큰 값이 반복마다 뒤로 밀려 마지막 위치가 확정된다.
swap 없으면 조기 종료할 수 있다
Selection
최솟값 선택
남은 구간에서 최솟값을 찾아 앞쪽 확정 구간에 놓는다.
보통 stable이 아니다
Insertion
정렬 구간 확장
현재 값을 앞쪽 정렬 구간의 맞는 위치에 끼워 넣는다.
거의 정렬된 입력에 강하다
경계
작은 입력
빈 배열과 길이 1 배열에서 loop가 불필요하게 돌지 않아야
한다.
인덱스 음수 접근을 조심한다