Dutch National Flag Algorithm을 통한 O(1) 공간 복잡도 One-pass 정렬 구현

Context

0, 1, 2 세 가지 값만 존재하는 배열을 In-place로 정렬해야 하는 제약 조건 발생. 단순 Counting 방식은 시간 복잡도 O(N)과 공간 복잡도 O(1)을 만족하나, 전체 배열을 두 번 순회해야 하는 Two-pass 구조의 한계 존재.

Technical Solution

• Three-pointer 전략을 통한 배열의 0, 1, 2 영역으로의 실시간 Partitioning 설계
• low 포인터를 활용한 0-region의 경계 확정 및 요소 배치
• high 포인터를 이용한 2-region의 역방향 배치로 불필요한 데이터 이동 최소화
• mid 포인터를 통한 현재 요소의 값 판별 및 영역별 Swap 로직 수행
• 0-region 배치 시 mid 포인터를 함께 증가시켜 중복 검사 제거
• 2-region 배치 시 Swap 된 요소의 재검증을 위해 mid 포인터 유지 전략 채택