ในการออกแบบอัลกอริธึม การปรับปรุงการแบ่งส่วน ( partition refinement)เป็นเทคนิคในการแสดงการแบ่งส่วนของเซตในรูปโครงสร้างข้อมูลที่ช่วยให้สามารถปรับปรุงการแบ่งส่วนได้โดยการแบ่งเซตย่อยออกเป็นเซตย่อยจำนวนมากขึ้น ในแง่นี้ มันจึงเป็นคู่ตรงข้ามกับโครงสร้างข้อมูลยูเนียน-ฟิวด์ (union-find)ซึ่งก็รักษาการแบ่งส่วนออกเป็นเซตที่ไม่ซ้ำกันเช่นกัน แต่การดำเนินการในยูเนียน-ฟิวด์จะรวมเซตเป็นคู่ๆ เข้าด้วยกัน ในบางแอปพลิเคชันของการปรับปรุงการแบ่งส่วน เช่นการค้นหาแบบกว้างตามลำดับตัวอักษร (lexicographic breadth-first search ) โครงสร้างข้อมูลยังคงรักษาลำดับของเซตในการแบ่งส่วนไว้ด้วย

การปรับปรุงพาร์ติชันถือเป็นองค์ประกอบสำคัญของอัลกอริธึมที่มีประสิทธิภาพหลายอย่างบนกราฟและออโตมาตาจำกัดรวมถึงการลด DFAอัลกอริธึม Coffman–Grahamสำหรับการจัดตารางเวลาแบบขนาน และการค้นหาแบบกว้างตามลำดับตัวอักษรของกราฟ^{[ 1 ] [ 2 ] [ 3 ]}

อัลกอริทึมการปรับปรุงพาร์ติชันจะรักษาตระกูลของเซตที่ไม่ซ้ำกันS_{_i} ไว้ ในตอนเริ่มต้นของอัลกอริทึม ตระกูลนี้จะมีเซตเดียวขององค์ประกอบทั้งหมดในโครงสร้างข้อมูล ในแต่ละขั้นตอนของอัลกอริทึม เซตXจะถูกนำเสนอให้กับอัลกอริทึม และแต่ละเซตS _{_i}ในตระกูลที่ประกอบด้วยสมาชิกของXจะถูกแบ่งออกเป็นสองเซต คือส่วนร่วมS_{_i} ∩ Xและส่วนต่างS _{_i} ∩ X

อัลกอริทึมดังกล่าวสามารถนำไปใช้ได้อย่างมีประสิทธิภาพโดยการรักษาโครงสร้างข้อมูลที่แสดงข้อมูลต่อไปนี้: ^{[ 4 ] [ 5 ]}

• ลำดับของเซตS _iในตระกูล ในรูปแบบเช่นรายการเชื่อมโยงสองทางที่อนุญาตให้แทรกเซตใหม่เข้าไปตรงกลางของลำดับได้
• แต่ละเซตSi จะมี ชุดขององค์ประกอบในเซต นั้น _ๆโดย อาจจัด เก็บในรูปแบบรายการเชื่อมโยงสองทางหรือโครงสร้างข้อมูลแบบอาร์เรย์ซึ่งช่วยให้สามารถลบองค์ประกอบแต่ละรายการออกจากชุดได้อย่างรวดเร็ว หรืออีกทางเลือกหนึ่ง โครงสร้างข้อมูลส่วนนี้อาจแสดงโดยการจัดเก็บองค์ประกอบทั้งหมดของทุกเซตไว้ในอาร์เรย์เดียว โดยเรียงลำดับตามเซตที่องค์ประกอบนั้น ๆ สังกัดอยู่ และแสดงชุดขององค์ประกอบในเซต Si ใด ๆ_ด้วยตำแหน่งเริ่มต้นและตำแหน่งสิ้นสุดในอาร์เรย์นี้
• แต่ละองค์ประกอบจะเกี่ยวข้องกับชุดที่องค์ประกอบนั้นสังกัดอยู่

ในการดำเนินการปรับปรุงแก้ไข อัลกอริทึมจะวนลูปผ่านองค์ประกอบของเซตX ที่กำหนด สำหรับแต่ละองค์ประกอบx ดังกล่าว _อัลกอริทึมจะค้นหาเซต Si ที่มี x อยู่ และตรวจสอบว่าได้มีการสร้างเซตที่สองสำหรับ Si ∩ _Xแล้วหรือไม่ถ้ายังไม่มี_อัลกอริทึมจะสร้างเซตที่สองและเพิ่มSi ลง ในรายการLของเซตที่ถูกแยกโดยการดำเนินการ จากนั้น ไม่ว่าจะมีเซตใหม่เกิดขึ้นหรือไม่ อัลกอริทึมจะลบx ออกจาก Si และเพิ่มลงใน Si ∩ _Xในการแสดงผลที่_เก็บองค์ประกอบทั้งหมดไว้ในอาร์เรย์เดียว การย้ายxจากเซตหนึ่งไปยังอีกเซตหนึ่งอาจทำได้โดยการสลับxกับองค์ประกอบสุดท้ายของSiแล้วลดดัชนีสุดท้ายของ_Siและดัชนีเริ่มต้นของเซตใหม่ลง สุดท้าย หลังจากประมวลผล องค์ประกอบทั้งหมดของ X ด้วยวิธีนี้แล้ว อัลกอริทึมจะวนลูปผ่าน L แยกเซต Siปัจจุบันแต่ละเซตออก_{จากเซต}ที่สองที่ถูกแยกออกมา และรายงานว่าทั้งสองเซตนี้เป็นเซตที่สร้างขึ้นใหม่โดยการดำเนินการปรับปรุงแก้ไข

เวลาที่ใช้ในการดำเนินการปรับปรุงข้อมูลเพียงครั้งเดียวด้วยวิธีนี้คือO (| X |)ซึ่งไม่ขึ้นอยู่กับจำนวนองค์ประกอบในกลุ่มเซตและไม่ขึ้นอยู่กับจำนวนเซตทั้งหมดในโครงสร้างข้อมูล ดังนั้น เวลาสำหรับลำดับการปรับปรุงข้อมูลจึงเป็นสัดส่วนกับขนาดรวมของเซตที่ป้อนให้กับอัลกอริทึมในแต่ละขั้นตอนการปรับปรุงข้อมูล

การประยุกต์ใช้การปรับปรุงการแบ่งส่วนในยุคแรกๆ พบได้ในอัลกอริทึมของHopcroft (1971)สำหรับการลดขนาดของ DFAในปัญหานี้ จะได้รับออโตมาตาจำกัดเชิงกำหนด เป็นอินพุต และต้องหาออโตมาตาที่เทียบเท่ากันโดยมีสถานะน้อยที่สุดเท่าที่จะเป็นไปได้ อัลกอริทึมของ Hopcroft รักษาการแบ่งส่วนของสถานะของออโตมาตาอินพุตออกเป็นเซตย่อย โดยมีคุณสมบัติว่าสถานะสองสถานะใดๆ ในเซตย่อยที่แตกต่างกันจะต้องถูกแมปไปยังสถานะที่แตกต่างกันของออโตมาตาเอาต์พุต ในขั้นต้นจะมีสองเซตย่อย เซตหนึ่งประกอบด้วยสถานะที่ยอมรับได้ทั้งหมดของออโตมาตา และอีกเซตหนึ่งประกอบด้วยสถานะที่เหลือ ในแต่ละขั้นตอน จะเลือกเซตย่อย Si หนึ่ง_เซตและ_{สัญลักษณ์}อินพุตx หนึ่ง ตัวของออโตมาตา จากนั้นเซตย่อยของสถานะจะถูกปรับปรุงให้เป็นสถานะที่การเปลี่ยนผ่านที่ติดป้ายกำกับxจะนำไปสู่​​Siและสถานะที่ การเปลี่ยนผ่าน xจะนำไปสู่ที่อื่น เมื่อเซตS _iที่ถูกเลือกไว้แล้วถูกแบ่งออกโดยการปรับปรุง เซตที่ได้ผลลัพธ์เพียงหนึ่งในสองเซต (เซตที่เล็กกว่า) เท่านั้นที่ต้องถูกเลือกอีกครั้ง ด้วยวิธีนี้ แต่ละสถานะจะมีส่วนร่วมในเซตXเป็นเวลาO ( s log n )ขั้นตอนการปรับปรุง และอัลกอริทึมโดยรวมใช้เวลาO ( ns log n )โดยที่nคือจำนวนสถานะเริ่มต้น และsคือขนาดของตัวอักษร^{[ 6 ]}

Sethi (1976)ได้นำการปรับปรุงพาร์ติชันมาใช้ในการใช้ งานอั ลกอริทึม Coffman–Graham อย่างมีประสิทธิภาพ สำหรับการจัดตารางเวลาแบบขนาน Sethi แสดงให้เห็นว่าสามารถใช้ในการสร้างลำดับโทโพโลยีที่เรียงลำดับตามพจนานุกรมของกราฟแบบไม่มีวงจรทิศทางที่กำหนดในเวลาเชิงเส้น การเรียงลำดับโทโพโลยีตามพจนานุกรมนี้เป็นหนึ่งในขั้นตอนสำคัญของอัลกอริทึม Coffman–Graham ในการประยุกต์ใช้นี้ องค์ประกอบของเซตที่ไม่ซ้ำกันคือจุดยอดของกราฟอินพุต และเซตXที่ใช้ในการปรับปรุงพาร์ติชันคือเซตของเพื่อนบ้านของจุดยอด เนื่องจากจำนวนเพื่อนบ้านทั้งหมดของจุดยอดทั้งหมดคือจำนวนขอบในกราฟ อัลกอริทึมจึงใช้เวลาเชิงเส้นตามจำนวนขอบ ซึ่งก็คือขนาดอินพุต^{[ 7 ]}

การปรับปรุงการแบ่งส่วนยังเป็นขั้นตอนสำคัญในการค้นหาแบบกว้างตามลำดับตัวอักษร ซึ่งเป็นอัลกอริธึมการค้นหากราฟที่มีการประยุกต์ใช้ในการระบุกราฟคอร์ดัลและกราฟประเภทสำคัญอื่นๆ อีกหลายประเภท อีกครั้งหนึ่ง องค์ประกอบของเซตที่ไม่ซ้ำกันคือจุดยอด และเซตXแทนเซตของเพื่อนบ้านดังนั้นอัลกอริธึมจึงใช้เวลาเชิงเส้น^{[ 8 ] [ 9 ]}