การจัดเรียงแบบ Bucket Sort และ Radix Sort

Bucket Sort & Radix Sort

เทคนิคของ Bucket คือเลขจะต้องเป็นจำนวนเต็มทั้งหมด สมมุติว่ามีเลข A1, A2, ..., An และในเลขชุดนี้ เรารู้ว่าทั้งหมดไม่มีค่าใดเลยที่มากกว่า M ดังนั้นเราจะสร้างอะเรย์ขนาด M ช่อง (เริ่มตั้งแต่ 1 ไปจนถึง M) ดังนี้

สมมุติว่าเรามีข้อมูลอยู่ 8 ตัวดังนี้

และต้องการจัดเรียงแบบ Bucket Sort สามารถทำได้ดังนี้

เตรียมอะเรย์ขนาด 10 ช่อง โดยแต่ละช่องเอาไว้สำหรับเก็บจำนวนตัวเลขที่พบ ดังนั้นอาจจะเริ่มต้นเป็น 0 หมดทุกช่องก็ได้

อ่านค่า 9 เข้ามา จะนำ 9 ไปนับเพิ่มขึ้นอีก 1 ไว้ที่ช่องที่ 9 ดังนี้

อ่านค่า 9 เข้ามาอีกตัว จะนำ 9 ไปนับเพิ่มขึ้นอีก 1 ที่ช่องที่ 9 ดังนี้

อ่านค่า 7 เข้ามาอีกตัว จะนับเพิ่มอีก 1 ที่ช่อง 7 ดังนี้

อ่านค่า 6, 0, 1, 4, 3 จนครบทุกรายการ จะได้จำนวนนับไว้ในแต่ละช่องดังนี้

เมื่อเราต้องการได้ค่าที่จัดเรียงเสร็จแล้ว เราจะอ่านข้อมูลจากอะเรย์ไล่มาตั้งแต่ช่องแรกจนถึงช่องสุดท้าย ถ้าช่องไหนที่มีค่ามากกว่า 0 เราจะพิมพ์หมายเลขช่องนั้นออกมาตามจำนวนที่นับไว้ ซึ่งเมื่อพิมพ์ออกมาจนครบจะได้ผลลัพธ์ดังนี้

0, 1, 3, 4, 6, 7, 9, 9