การคัดแยกลูกปัด

การเรียงลำดับแบบลูกปัดหรือที่เรียกว่าการเรียงลำดับแบบแรงโน้มถ่วงเป็นอัลกอริทึมการเรียงลำดับแบบธรรมชาติ พัฒนาโดยJoshua J. Arulanandham , Cristian S. CaludeและMichael J. Dinneenในปี 2002 และตีพิมพ์ในThe Bulletin of the European Association for Theoretical Computer Science [ ^{1 ] การ}ใช้งานฮาร์ดแวร์แบบดิจิทัลและอนาล็อกของการเรียงลำดับแบบลูกปัดสามารถบรรลุเวลาการเรียงลำดับO ( n ) ได้ อย่างไรก็ตาม การใช้งานอัลกอริทึมนี้ในซอฟต์แวร์ มักจะช้ากว่ามาก และสามารถใช้เรียงลำดับรายการของจำนวนเต็มบวก เท่านั้น นอกจากนี้ ดูเหมือนว่าแม้ในกรณีที่ดีที่สุด อัลกอริทึมก็ต้องการพื้นที่ O ( n ^{2 )}

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

ถ้าเราปล่อยให้ลูกปัดตกลงมา แถวต่างๆ ก็จะแทนจำนวนเต็มเดียวกันในลำดับที่เรียงแล้ว แถวที่ 1 จะมีจำนวนมากที่สุดในชุด ขณะที่แถวที่nจะมีจำนวนน้อยที่สุด ถ้าหากปฏิบัติตามข้อกำหนดข้างต้นที่ระบุว่าแถวต่างๆ จะมีลูกปัดเรียงกันอยู่ที่เสา 1..k และเว้นเสาk +1..m ว่างไว้ ข้อกำหนดนี้ก็จะยังคงเป็นเช่นนั้นต่อไป

ในตัวอย่างทางกายภาพของเรา การปล่อยให้ลูกปัด "ตกลงมา" ทำให้ค่าที่มากขึ้นจากแถวบนๆ แพร่กระจายไปยังแถวล่างๆ ถ้าค่าที่แสดงโดยแถวaน้อยกว่าค่าที่อยู่ในแถวa+1ลูกปัดบางส่วนจากแถวa+1จะตกลงไปในแถวaซึ่งเป็นสิ่งที่เกิดขึ้นอย่างแน่นอน เพราะแถวaไม่มีลูกปัดอยู่ในตำแหน่งที่จะหยุดลูกปัดจากแถวa+1ไม่ให้ตกลงมาได้

กลไกพื้นฐานของการเรียงลำดับด้วยลูกปัดนั้นคล้ายคลึงกับกลไกเบื้องหลังการเรียงลำดับด้วยการนับ กล่าวคือ จำนวนลูกปัดบนแต่ละขั้วจะสอดคล้องกับจำนวนองค์ประกอบที่มีค่าเท่ากับหรือมากกว่าดัชนีของขั้วนั้น

การจัดเรียงลูกปัดสามารถทำได้โดยแบ่งระดับความซับซ้อนออกเป็น 4 ระดับหลักๆ ดังนี้:

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

เช่นเดียวกับอั ลกอริทึมการเรียงลำดับแบบรังนก พิราบ (Pigeonhole sort) การเรียงลำดับแบบลูกปัด ( Bead sort) นั้นมีความพิเศษตรงที่ในกรณีที่เลวร้ายที่สุด มันสามารถทำงานได้เร็วกว่าO ( n log n ) ซึ่งเป็นประสิทธิภาพที่เร็วที่สุดที่เป็นไปได้สำหรับการเรียงลำดับแบบเปรียบเทียบในกรณีที่เลวร้ายที่สุด เป็นไปได้เพราะคีย์สำหรับการเรียงลำดับแบบลูกปัดเป็นจำนวนเต็มบวกเสมอ และการเรียงลำดับแบบลูกปัดใช้ประโยชน์จากโครงสร้างของมัน

โค้ดนี้เขียนด้วยภาษา Pythonโดยสมมติว่าข้อมูลที่input_listส่งเข้ามาจะเป็นลำดับของจำนวนเต็ม ฟังก์ชันนี้จะส่งคืนลิสต์ใหม่แทนที่จะแก้ไขลิสต์เดิม แต่สามารถปรับเปลี่ยนได้อย่างง่ายดายเพื่อให้ทำงานได้อย่างมีประสิทธิภาพโดยไม่ต้องแก้ไขลิสต์เดิม

def beadsort ( input_list ): """การเรียงลำดับลูกปัด.""" return_list = [] # เริ่มต้น 'รายการที่สลับแถวและคอลัมน์' ให้มีจำนวนองค์ประกอบเท่ากับ# ค่าสูงสุดของอินพุต -- โดยพื้นฐานแล้วคือการนำคอลัมน์ที่ 'สูงที่สุด' # ของลูกปัดอินพุตมาวางราบtransposed_list = [ 0 ] * max ( input_list ) for num in input_list : # สำหรับแต่ละองค์ประกอบ (แต่ละ 'คอลัมน์ของลูกปัด') ของรายการอินพุต# 'วางลูกปัดราบ' โดยการเพิ่มจำนวนองค์ประกอบของ# รายการที่สลับแถวและคอลัมน์ให้เท่ากับความสูงของคอลัมน์# สิ่งเหล่านี้จะสะสมอยู่ด้านบนของการเพิ่มก่อนหน้าtransposed_list [: num ] = [ n + 1 for n in transposed_list [: num ]] # ตอนนี้เราได้ทิ้งลูกปัดแล้ว ในการยกเลิกการสลับแถวและคอลัมน์ เราจะนับ# 'แถวล่างสุด' ของลูกปัดที่ทิ้ง จากนั้นจำลองการลบ# แถวนี้โดยการลบ 1 ออกจากแต่ละ 'คอลัมน์' ของรายการที่สลับแถวและคอลัมน์# เมื่อคอลัมน์ไม่ถึงความสูงที่เพียงพอสำหรับแถวปัจจุบัน# ค่าของมันใน transposed_list จะน้อยกว่าหรือเท่ากับ 0 สำหรับi ในช่วง( len ( input_list )): # การนับค่าที่มากกว่า i คือวิธีที่เราบอกจำนวนลูกปัดใน # 'แถวล่างสุด' ปัจจุบันโปรดทราบว่าค่าบูลีนของ Python สามารถ# ประเมินเป็นจำนวนเต็มได้ True == 1 และ False == 0 return_list.append ( sum ( n > i for n in transposed_list )) # รายการผลลัพธ์ จะถูกเรียงลำดับจากมากไปน้อยreturn return_list

เราสามารถนำอัลกอริทึมไปใช้โดยใช้Java ได้ เช่นกัน ^{[ 2 ]}

public static void beadSort ( int [] a ) { // ค้นหาองค์ประกอบที่มากที่สุดint max = a [ 0 ] ; for ( int i = 1 ; i < a . length ; i ++ ) { if ( a [ i ] > max ) { max = a [ i ] ; } } // จัดสรรหน่วยความจำint [][] beads = new int [ a . length ][ max ] ; // ทำเครื่องหมายลูกปัดfor ( int i = 0 ; i < a . length ; i ++ ) { for ( int j = 0 ; j < a [ i ] ; j ++ ) { beads [ i ][ j ] = 1 ; } } // เลื่อนลูกปัดลงfor ( int j = 0 ; j < max ; j ++ ) { int sum = 0 ; สำหรับ( int i = 0 ; i < a.length ; i ++ ) { sum + = beads [ i ] [ j ] ; beads [ i ] [ j ] = 0 ; } สำหรับ( int i = a.length - 1 ; i > = a.length - sum ; i-- ) { a​​​[ i ] = j + 1 ; } } }

• "Bead-Sort: A Natural Sorting Algorithm" (PDF) . เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2017-08-09 . เรียกดูเมื่อ2005-01-01 . (114  กิโลไบต์ )
• การเรียงลำดับลูกปัดใน MGS ( เก็บถาวรเมื่อ 2011-07-28 ที่Wayback Machine)เป็นภาพแสดงการเรียงลำดับลูกปัดที่นำมาใช้ในภาษาโปรแกรมMGS (เก็บถาวรเมื่อ 2009-06-14 ที่Wayback Machine)
• การจัดเรียงลูกปัดบน MathWorld
• การแสดงภาพเชิงโต้ตอบของการคัดแยกลูกปัด