ปัญหาธงชาติเนเธอร์แลนด์ [ ^{1 ] เป็น}ปัญหาการคำนวณที่เสนอโดยEdsger Dijkstra [ ^{2 ] ธงชาติ}เนเธอร์แลนด์ประกอบด้วยสามสี ได้แก่ สีแดง สีขาว และสีน้ำเงิน กำหนดให้ลูกบอลสามสีนี้เรียงกันแบบสุ่มเป็นแถว (ไม่สำคัญว่าจะมีลูกบอลกี่ลูก) งานคือการจัดเรียงลูกบอลเหล่านั้นให้ลูกบอลสีเดียวกันอยู่ด้วยกัน และกลุ่มสีของลูกบอลเหล่านั้นอยู่ในลำดับที่ถูกต้อง

วิธีแก้ปัญหานี้มีความน่าสนใจสำหรับการออกแบบอัลกอริธึมการเรียงลำดับโดยเฉพาะอย่างยิ่ง อัลกอริธึม quicksort เวอร์ชันต่างๆ ที่ต้องมีความทนทานต่อองค์ประกอบที่ซ้ำกันอาจใช้ฟังก์ชันการแบ่งพาร์ติชันแบบสามทางที่จัดกลุ่มรายการที่น้อยกว่าคีย์ที่กำหนด (สีแดง) เท่ากับคีย์ (สีขาว) และมากกว่าคีย์ (สีน้ำเงิน) มีวิธีแก้ปัญหาหลายวิธีที่มีลักษณะการทำงานที่แตกต่างกัน ซึ่งปรับให้เหมาะสมกับการเรียงลำดับอาร์เรย์ที่มีองค์ประกอบที่ซ้ำกันจำนวนน้อยหรือมาก^{[ 3 ]}

ปัญหานี้สามารถมองได้ในแง่ของการจัดเรียงองค์ประกอบของอาร์เรย์ใหม่ สมมติว่าแต่ละองค์ประกอบที่เป็นไปได้สามารถจัดอยู่ในหนึ่งในสามประเภท (ล่าง กลาง และบน) ได้อย่างแน่นอน ตัวอย่างเช่น ถ้าองค์ประกอบทั้งหมดอยู่ในช่วง 0 ถึง 1 องค์ประกอบล่างอาจกำหนดให้เป็นองค์ประกอบในช่วง 0 ถึง 0.25 (ไม่รวม 0.25) องค์ประกอบกลางเป็น 0.25 ถึง 0.5 (ไม่รวม 0.5) และองค์ประกอบบนเป็น 0.5 ขึ้นไป (การเลือกค่าเหล่านี้แสดงให้เห็นว่าช่วงของแต่ละประเภทไม่จำเป็นต้องเท่ากัน) ปัญหาคือการสร้างอาร์เรย์ที่องค์ประกอบ "ล่าง" ทั้งหมดอยู่ก่อน (มีดัชนีน้อยกว่าดัชนีของ) องค์ประกอบ "กลาง" ทั้งหมด ซึ่งอยู่ก่อนองค์ประกอบ "บน" ทั้งหมด

อัลกอริทึมหนึ่งคือการให้กลุ่มบนเติบโตลงมาจากด้านบนของอาร์เรย์ กลุ่มล่างเติบโตขึ้นจากด้านล่าง และเก็บกลุ่มกลางไว้เหนือกลุ่มล่างเล็กน้อย อัลกอริทึมจะจัดทำดัชนีสามตำแหน่ง ได้แก่ ด้านล่างของกลุ่มบน ด้านบนของกลุ่มล่าง และด้านบนของกลุ่มกลาง องค์ประกอบที่ยังไม่ได้เรียงลำดับจะอยู่ระหว่างกลุ่มกลางและกลุ่มบน^{[ 4 ]}ในแต่ละขั้นตอน ให้ตรวจสอบองค์ประกอบที่อยู่เหนือกลุ่มกลางเล็กน้อย หากเป็นของกลุ่มบน ให้สลับกับองค์ประกอบที่อยู่ต่ำกว่ากลุ่มบน หากเป็นของกลุ่มล่าง ให้สลับกับองค์ประกอบที่อยู่เหนือกลุ่มล่างเล็กน้อย หากอยู่ในกลุ่มกลาง ให้คงไว้ อัปเดตดัชนีที่เหมาะสม ความซับซ้อนคือ Θ(n) การเคลื่อนย้ายและการตรวจสอบ^{[ 1 ]}

ขั้นตอนการแบ่งพาร์ติชันสามทาง (A : อาร์เรย์ของค่า, mid : ค่า): i ← 0 j ← 0 k ← ขนาดของ A - 1 ในขณะที่ j <= k: ถ้า A[j] < mid: สลับ A[i] และ A[j] i ← i + 1 j ← j + 1 มิฉะนั้น ถ้า A[j] > mid ให้ สลับ A[j] และ A[k] k ← k - 1 อื่น : j ← j + 1

• การจัดเรียงธงชาติอเมริกัน
• ธงชาติเนเธอร์แลนด์

• คำอธิบายและการสาธิตการทำงานของอัลกอริทึมแบบโต้ตอบสำหรับการเรียงลำดับสีสองหรือสามสี