네덜란드 국기 문제
Dutch national flag problem |
네덜란드 국기문제는[1] 에드제르 디크스트라가 제안한 컴퓨터 과학 프로그래밍 문제다.[2] 네덜란드의 국기는 빨강, 흰색, 파랑의 세 가지 색으로 구성되어 있다. 이 세 가지 색상의 공들이 한 줄로 랜덤하게 배열되어 있는 경우(볼이 몇 개 있는지는 중요하지 않다) 같은 색상의 모든 공들이 함께 있고 집합적인 색 그룹들이 올바른 순서로 배열되도록 하는 것이 과제다.
이 문제의 해결책은 정렬 알고리즘 설계에 관심이 있다. 특히 반복적인 요소에 견고해야 하는 퀵소트 알고리즘의 변형에서는 주어진 키(빨간색), 키(흰색)보다 크고 키(파란색)보다 큰 항목을 그룹화하는 3방향 분할 기능을 사용할 수 있다. 다양한 성능 특성을 가진 여러 솔루션이 존재하며, 반복 요소가 적거나 많은 배열로 정렬되도록 조정된다.[3]
배열 케이스
이 문제는 배열의 요소 재배열 측면에서도 볼 수 있다. 가능한 각 요소를 세 가지 범주(하단, 중간 및 상단) 중 하나로 정확하게 분류할 수 있다고 가정해 보십시오. 예를 들어, 모든 요소가 0 ... 1인 경우, 하단은 0 ... 0.25(0.25 포함하지 않음), 중위는 0.25 … 0.5(0.5 포함하지 않음), 상단은 0.5 이상(0.5 제외)의 원소로 정의할 수 있다. (이 값들의 선택은 범주가 동일한 범위가 될 필요가 없음을 보여준다.) 문제는 모든 "하단" 요소가 모든 "중간" 요소보다 앞에 오도록(지수보다 작은) 배열을 만드는 것이다. 모든 "상단" 요소보다 먼저 오는 "중간"
하나의 알고리즘은 상위 그룹이 배열의 위에서 아래로, 하위 그룹이 아래에서 위로 성장하도록 하는 것이며, 중간 그룹을 하위 그룹 바로 위에서 유지하도록 하는 것이다. 알고리즘은 상위 그룹의 하위 그룹, 하위 그룹의 상위 그룹, 중간 그룹의 상위 그룹 등 세 위치를 지수화한다. 아직 정렬되지 않은 요소들은 중간 그룹과 상위 그룹 사이에 들어간다.[4] 각 단계에서 중간 바로 위에 있는 요소를 검사하십시오. 상위 그룹에 속할 경우 상위 그룹 바로 아래의 요소와 교체하십시오. 하단에 속할 경우 하단의 바로 위에 있는 요소와 교체하십시오. 중간에 있으면 놔둬. 적절한 인덱스를 업데이트하십시오. 복잡성은 θ(n) 이동과 시험이다.[1]
가성음
제로 기반 어레이 인덱싱을 가정하는 3방향 파티셔닝에 대한 다음의 유사코드는 Dijkstra가 직접 제안했다.[2] 3가지 지수 i, j, k를 사용하며, i j j ≤ k라는 불변성을 유지한다.
- 0부터 (포함하지 않음) i까지의 항목은 중간보다 작은 값이다.
- i에서 j까지의 항목은 mid와 동일한 값이다.
- j에서 k까지의 항목은 아직 정렬되지 않은 값이며,
- k + 1에서 배열 끝까지의 항목은 중간보다 큰 값이다.
procedure three-way-partition(A : array of values, mid : value): i ← 0 j ← 0 k ← size of A - 1 while j <= k: if A[j] < mid: swap A[i] and A[j] i ← i + 1 j ← j + 1 else if A[j] > mid: swap A[j] and A[k] k ← k - 1 else: j ← j + 1
참고 항목
참조
- ^ a b "Dutch National Flag problem and algorithm". Faculty of Information Technology (Clayton), Monash University, Australia. 1998.
- ^ a b 1976년 그의 책 "프렌티스홀 프로그래밍의 규율"의 한 장에서
- ^ 후자의 경우는 멀티키 퀵소트로 문자열 정렬에서 발생한다. Kim, Eunsang; Park, Kunsoo (2009). "Improving multikey Quicksort for sorting strings with many equal elements". Information Processing Letters. 109 (9): 454–459. doi:10.1016/j.ipl.2009.01.007.
- ^
이 문서에는 NIST 문서의 공용 도메인 자료가 포함되어 있다.
이 문서에는 
