การคัดแยกแบบถัง

ระดับ	อัลกอริทึมการเรียงลำดับ
โครงสร้างข้อมูล	อาร์เรย์
ประสิทธิภาพในกรณีที่เลวร้ายที่สุด	${\displaystyle O\left(n^{2}\right)}$
ประสิทธิภาพโดยเฉลี่ย	${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$โดย ที่k คือจำนวนถัง${\displaystyle O(n),{\text{เมื่อ }}k\approx n}$
ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n+k)}$

การเรียงลำดับแบบถัง (Bucket sort ) หรือการเรียงลำดับแบบถัง (Bin sort ) เป็นอัลกอริทึมการเรียงลำดับที่ทำงานโดยการกระจายองค์ประกอบของอาร์เรย์ไปยังถังจำนวนหนึ่ง จากนั้นแต่ละถังจะถูกเรียงลำดับแยกกัน โดยอาจใช้อัลกอริทึมการเรียงลำดับอื่น หรือโดยการใช้อัลกอริทึมการเรียงลำดับแบบถังซ้ำๆ มันเป็นการเรียงลำดับแบบกระจาย (Distribution sort ) ซึ่งเป็นการขยายความของการเรียงลำดับแบบรังนกพิราบ (Pigeonhole sort)ที่อนุญาตให้มีหลายคีย์ต่อถัง และเป็นญาติกับ การเรียง ลำดับแบบฐานสิบ (Radix sort)ในรูปแบบจากหลักที่มีค่ามากที่สุดไปยังหลักที่มีค่าน้อยที่สุด การเรียงลำดับแบบถังสามารถนำไปใช้กับการเปรียบเทียบได้ ดังนั้นจึงอาจถือได้ว่าเป็นอัลกอริทึมการเรียงลำดับแบบเปรียบเทียบ เช่นกัน ความซับซ้อนในการคำนวณขึ้นอยู่กับอัลกอริทึมที่ใช้ในการเรียงลำดับแต่ละถัง จำนวนถังที่จะใช้ และว่าข้อมูลนำเข้ามีการกระจายอย่างสม่ำเสมอหรือไม่

การเรียงลำดับแบบ Bucket Sort ทำงานดังนี้:

1. สร้างอาร์เรย์ของ "ถัง" ที่ว่างเปล่าในตอนเริ่มต้น
2. กระจาย : ทำซ้ำขั้นตอนการจัดกลุ่มข้อมูลเดิม โดยนำวัตถุแต่ละชิ้นไปใส่ในช่องที่กำหนดไว้
3. จัดเรียงถังที่ไม่ว่างเปล่าแต่ละใบ
4. รวบรวม : เข้าไปที่ถังเก็บข้อมูลตามลำดับ และนำองค์ประกอบทั้งหมดกลับเข้าไปในอาร์เรย์เดิม

ฟังก์ชัน bucketSort(array, k) คือ ถัง ← อาร์เรย์ใหม่ของรายการว่าง k รายการ M ← 1 + ค่าคีย์สูงสุดในอาร์เรย์ สำหรับ i ตั้งแต่ 0 ถึงความยาวของอาร์เรย์ให้ แทรกอาร์เรย์[i]ลงในบัคเก็ต [floor(k × array[i] / M)] สำหรับ i ตั้งแต่ 0 ถึง k ให้ทำซ้ำ nextSort(buckets[i]) ส่งคืนการเชื่อมต่อของ bucket[0], ...., bucket[k] 

ให้arrayแทนอาร์เรย์ที่จะเรียงลำดับ และkแทนจำนวนบัคเก็ตที่จะใช้ เราสามารถคำนวณค่าคีย์สูงสุดได้ในเวลาเชิงเส้นโดยการวนซ้ำคีย์ทั้งหมดหนึ่งครั้งฟังก์ชัน floorต้องใช้ในการแปลงจำนวนทศนิยมเป็นจำนวนเต็ม (และอาจต้องมีการแปลงชนิดข้อมูลด้วย) ฟังก์ชันnextSortเป็นฟังก์ชันการเรียงลำดับที่ใช้ในการเรียงลำดับแต่ละบัคเก็ต โดยทั่วไป จะใช้การเรียงลำดับ แบบแทรก (insertion sort ) เนื่องจากมีประสิทธิภาพค่อนข้างสูงเมื่อมีจำนวนองค์ประกอบน้อย แต่ก็สามารถใช้อัลกอริทึมอื่นได้เช่นกัน เช่นการเรียงลำดับแบบเลือก (selection sort ) หรือ การเรียงลำดับแบบผสาน ( merge sort ) การใช้bucketSortเป็นnextSortจะได้ผลลัพธ์ที่คล้ายกับการเรียงลำดับแบบเรเดียล (radix sort ) โดยเฉพาะอย่างยิ่ง กรณีn = 2จะตรงกับquicksort (แม้ว่าอาจเลือก pivot ได้ไม่ดีนัก)

เมื่อข้อมูลนำเข้ามีคีย์หลายตัวที่อยู่ใกล้กัน (การจัดกลุ่ม) องค์ประกอบเหล่านั้นมีแนวโน้มที่จะถูกจัดไว้ในบัคเก็ตเดียวกัน ซึ่งส่งผลให้บางบัคเก็ตมีจำนวนองค์ประกอบมากกว่าค่าเฉลี่ย สถานการณ์ที่เลวร้ายที่สุดคือเมื่อองค์ประกอบทั้งหมดถูกจัดไว้ในบัคเก็ตเดียว ประสิทธิภาพโดยรวมก็จะขึ้นอยู่กับอัลกอริทึมที่ใช้ในการจัดเรียงแต่ละบัคเก็ต เช่น อัลกอริทึมการ เรียง ลำดับแบบแทรก หรือ อัลกอริทึมการ เรียงลำดับแบบเปรียบเทียบเช่นการ เรียงลำดับแบบผสาน${\displaystyle O(n^{2})}$${\displaystyle O(n\log(n))}$

พิจารณากรณีที่ข้อมูลนำเข้ามีการกระจายแบบสม่ำเสมอ ขั้นตอนแรกคือการกำหนดค่าเริ่มต้นให้กับบัคเก็ตและค้นหาค่าคีย์สูงสุดในอาร์เรย์ ซึ่งสามารถทำได้ในเวลา ถ้าการหารและการคูณสามารถทำได้ในเวลาคงที่การกระจายแต่ละองค์ประกอบไปยังบัคเก็ตก็ใช้เวลาเช่นกัน สมมติ ว่าใช้การเรียงลำดับแบบแทรก (insertion sort) เพื่อเรียงลำดับแต่ละบัคเก็ต ขั้นตอนที่สามจะใช้เวลาโดยที่คือความยาวของบัคเก็ตที่มีดัชนีเนื่องจากเรากำลังพิจารณาเวลาเฉลี่ยจึงต้องประเมินค่าคาดหวังแทน ให้เป็นตัวแปรสุ่มที่มีค่าถ้าองค์ประกอบถูกวางไว้ในบัคเก็ตและถ้าไม่ใช่ เราจะได้ดังนั้น ${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$${\displaystyle n_{i}}$${\displaystyle i}$${\displaystyle E(n_{i}^{2})}$${\displaystyle X_{ij}}$${\displaystyle 1}$${\displaystyle j}$${\displaystyle i}$${\displaystyle 0}$${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right).\end{aligned}}}$

บรรทัดสุดท้ายแยกผลรวมออกเป็นกรณีและกรณีเนื่องจากโอกาสที่วัตถุจะถูกกระจายไปยังถังคือดังนั้นจะเป็น 1 ด้วยความน่าจะเป็นและ 0 ในกรณีอื่น ๆ ${\displaystyle j=l}$${\displaystyle j\neq l}$${\displaystyle i}$${\displaystyle 1/k}$${\displaystyle X_{ij}}$${\displaystyle 1/k}$

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}}$

เมื่อรวมผลลัพธ์แล้ว จะได้ว่า

${\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

สุดท้ายแล้ว ความซับซ้อนจะเป็นดังนี้ ${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)}$

ขั้นตอนสุดท้ายของการเรียงลำดับแบบบัคเก็ต ซึ่งก็คือการรวมวัตถุที่เรียงลำดับทั้งหมดในแต่ละบัคเก็ตเข้าด้วยกัน ต้องใช้เวลา ดังนั้น ความซับซ้อนโดยรวมจึงเป็นโปรดทราบว่าหากเลือก k ให้เป็นการเรียงลำดับแบบบัคเก็ตจะทำงานในเวลาเฉลี่ย โดยกำหนดให้ข้อมูลนำเข้ามีการกระจายอย่างสม่ำเสมอ^{[ 1 ]}${\displaystyle O(k)}$${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$${\displaystyle k=\Theta (n)}$${\displaystyle O(n)}$

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

หากทราบหรือสามารถประมาณการการกระจายของข้อมูลขาเข้าได้ มักจะสามารถเลือกถังเก็บข้อมูลที่มีความหนาแน่นคงที่ (แทนที่จะมีขนาดคงที่เพียงอย่างเดียว) ซึ่งจะช่วยให้ได้ความซับซ้อนของเวลาโดยเฉลี่ยแม้ว่าข้อมูลขาเข้าจะไม่กระจายอย่างสม่ำเสมอ ${\displaystyle O(n)}$

รูปแบบที่พบได้บ่อยที่สุดของการเรียงลำดับแบบบัคเก็ตจะทำงานกับรายการ อินพุตตัวเลข nตัวระหว่างศูนย์และค่าสูงสุดMและแบ่งช่วงค่าออกเป็นbบัคเก็ต โดยแต่ละบัคเก็ตมีขนาดM / bหากแต่ละบัคเก็ตได้รับการเรียงลำดับโดยใช้การเรียงลำดับแบบแทรกการเรียงลำดับจะแสดงให้เห็นว่าทำงานในเวลาเชิงเส้นที่คาดหวัง (โดยเฉลี่ยจากอินพุตที่เป็นไปได้ทั้งหมด) ^{[ 3 ]}อย่างไรก็ตาม ประสิทธิภาพของการเรียงลำดับนี้จะลดลงเมื่อมีการรวมกลุ่ม หากค่าจำนวนมากอยู่ใกล้กัน ค่าเหล่านั้นจะตกอยู่ในบัคเก็ตเดียวกันและเรียงลำดับช้าลง การลดลงของประสิทธิภาพนี้จะถูกหลีกเลี่ยงในอัลกอริทึมการเรียงลำดับแบบบัคเก็ตดั้งเดิมโดยการสมมติว่าอินพุตถูกสร้างขึ้นโดยกระบวนการสุ่มที่กระจายองค์ประกอบอย่างสม่ำเสมอในช่วง[0,1 ) ^{[ 1 ]}

เช่นเดียวกับการเรียงลำดับแบบ bucket sort ทั่วไปที่อธิบายไว้ข้างต้นProxmapSortทำงานโดยการแบ่งอาร์เรย์ของคีย์ออกเป็นอาร์เรย์ย่อยโดยใช้ฟังก์ชัน "map key" ที่รักษาลำดับบางส่วนของคีย์ไว้ เมื่อเพิ่มคีย์แต่ละตัวลงในอาร์เรย์ย่อย จะใช้การเรียงลำดับแบบแทรก (insertion sort) เพื่อรักษาลำดับของอาร์เรย์ย่อยนั้น ส่งผลให้ทั้งอาร์เรย์อยู่ในลำดับที่เรียงแล้วเมื่อ ProxmapSort ทำงานเสร็จสิ้น ProxmapSort แตกต่างจาก bucket sort ตรงที่ใช้ map key เพื่อวางข้อมูลในตำแหน่งโดยประมาณที่ควรอยู่ในลำดับที่เรียงแล้ว ทำให้เกิด "proxmap" ซึ่งเป็นการแมปความใกล้เคียงของคีย์

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

การเรียงลำดับของบุรุษไปรษณีย์เป็นรูปแบบหนึ่งของการเรียงลำดับแบบถังที่ใช้ประโยชน์จากโครงสร้างลำดับชั้นขององค์ประกอบ ซึ่งโดยทั่วไปจะอธิบายโดยชุดของคุณลักษณะ นี่คืออัลกอริทึมที่ใช้โดยเครื่องคัดแยกจดหมายในที่ทำการไปรษณีย์ : จดหมายจะถูกคัดแยกก่อนระหว่างภายในประเทศและต่างประเทศ จากนั้นตามรัฐ จังหวัด หรือเขตแดน จากนั้นตามที่ทำการไปรษณีย์ปลายทาง จากนั้นตามเส้นทาง ฯลฯ เนื่องจากคีย์จะไม่ถูกเปรียบเทียบกัน เวลาในการเรียงลำดับจึงเป็น O( cn ) โดยที่cขึ้นอยู่กับขนาดของคีย์และจำนวนถัง ซึ่งคล้ายกับการเรียงลำดับแบบเรดิกซ์ที่ทำงาน "จากบนลงล่าง" หรือ "หลักที่มีนัยสำคัญมากที่สุดก่อน" ^{[ 5 ] [ 6 ]}

การเรียงลำดับแบบสับเปลี่ยน^{[ 7 ]}เป็นรูปแบบหนึ่งของการเรียงลำดับแบบถังที่เริ่มต้นด้วยการลบรายการ 1/8 แรกของรายการnรายการที่จะเรียงลำดับ เรียงลำดับรายการเหล่านั้นแบบเรียกซ้ำ และใส่ลงในอาร์เรย์ ซึ่งจะสร้าง "ถัง" n /8 ถัง ซึ่งจะกระจายรายการที่เหลือ 7/8 ลงไป จากนั้นแต่ละ "ถัง" จะถูกเรียงลำดับ และ "ถัง" เหล่านั้นจะถูกรวมเข้าด้วยกันเป็นอาร์เรย์ที่เรียงลำดับแล้ว

การเรียงลำดับแบบ Bucket Sort สามารถมองได้ว่าเป็นการขยายความของการเรียงลำดับแบบ Counting Sort ; ในความเป็นจริง หากแต่ละ Bucket มีขนาด 1 การเรียงลำดับแบบ Bucket Sort จะลดรูปไปเป็นการเรียงลำดับแบบ Counting Sort ขนาด Bucket ที่แปรผันได้ของการเรียงลำดับแบบ Bucket Sort ช่วยให้ใช้หน่วยความจำ O( n ) แทนที่จะเป็น O( M ) โดยที่Mคือจำนวนค่าที่แตกต่างกัน ในทางกลับกัน มันจะสูญเสียพฤติกรรมกรณีที่เลวร้ายที่สุด O( n + M ) ของการเรียงลำดับแบบ Counting Sort ไป

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

อั ลกอริทึม mergesort แบบ nทางก็เริ่มต้นด้วยการกระจายรายการออกเป็นnรายการย่อย และเรียงลำดับแต่ละรายการย่อยเช่นกัน อย่างไรก็ตาม รายการย่อยที่สร้างโดย mergesort มีช่วงค่าที่ทับซ้อนกัน ดังนั้นจึงไม่สามารถรวมเข้าด้วยกันได้ด้วยการต่อแบบง่ายๆ เหมือนใน bucket sort แต่ต้องใช้อัลกอริทึม merge เข้ามาสลับกันแทน อย่างไรก็ตาม ค่าใช้จ่ายที่เพิ่มขึ้นนี้ได้รับการชดเชยด้วยขั้นตอนการกระจายที่ง่ายกว่า และความสามารถในการรับประกันว่าแต่ละรายการย่อยมีขนาดเท่ากัน ซึ่งทำให้ได้ขอบเขตเวลาที่ดีที่สุดในกรณีที่เลวร้ายที่สุด

การเรียงลำดับแบบรากที่สอง จากบนลงล่าง (Top-down radix sort)สามารถมองได้ว่าเป็นกรณีพิเศษของการเรียงลำดับแบบถัง (bucket sort) โดยที่ช่วงของค่าและจำนวนถังถูกจำกัดให้เป็นกำลังของสอง ดังนั้น ขนาดของแต่ละถังจึงเป็นกำลังของสองเช่นกัน และสามารถใช้กระบวนการนี้แบบเรียกซ้ำได้ วิธีการนี้สามารถเร่งความเร็วในขั้นตอนการกระจายได้ เนื่องจากเราจำเป็นต้องตรวจสอบเพียงคำนำหน้าของการแสดงบิตของแต่ละองค์ประกอบเพื่อกำหนดถังของมันเท่านั้น

• รหัสเรียงลำดับบัคเก็ตสำหรับ ANSI C
• รูปแบบต่างๆ ของการเรียงลำดับแบบ Bucket Sort พร้อมตัวอย่างสาธิต