การเรียงลำดับแบบลูกปัด

การจัดเรียงแบบลูกปัด หรือที่เรียกอีกชื่อว่า การจัดเรียงแบบแรงโน้มถ่วง เป็นขั้นตอนวิธีการเรียงลำดับแบบธรรมชาติ พัฒนาโดย Joshua J. Arulanandham, Cristian S. Calude และ Michael J. Dinneen ในปี ค.ศ.2002

ใส่ลูกปัดตามข้อมูลที่มี

ทำการจัดเรียง

ลักษณะการทำงาน

การจัดเรียงแบบลูกปัดเริ่มแรกโดยให้จำนวนเสาที่ใส่ลูกปัดเท่ากับค่าของข้อมูลตัวนั้นๆ โดยจำนวนแถวแนวตั้งเท่ากับจำนวนทั้งหมดของข้อมูลที่ต้องการจะเรียงลำดับ เมื่อใส่ลูกปัดตามข้อมูลที่มีอยู่จนครบแล้ว ลูกที่ลอยอยู่โดยไม่มีอะไรรองรับจะตกลงโดยแรงโน้มถ่วง

ความซับซ้อนของการทำงาน

O(1) : ลูกปัดทั้งหมดเคลื่อนที่พร้อมกันในหน่วยเวลาเดียวกันเช่นเดียวกับตัวอย่างทางกายภาพที่เรียบง่ายข้างต้น นี่คือความซับซ้อนที่เป็นนามธรรมและไม่สามารถนำไปปฏิบัติได้

O(√n) : ในรูปแบบทางกายภาพที่สมจริงที่ใช้แรงโน้มถ่วงเวลาที่ใช้ในการปล่อยให้ลูกปัดตกลงมาเป็นสัดส่วนกับรากที่สองของความสูงสูงสุดซึ่งเป็นสัดส่วนกับ n (จำนวนข้อมูลทั้งหมด)

O(n) : ลูกปัดจะถูกย้ายไปทีละแถว นี่คือกรณีที่ใช้ในโซลูชั่นฮาร์ดแวร์อนาล็อกและดิจิตอล

O(S) : โดย S คือผลรวมของจำนวนเต็มในชุดข้อมูล ลูกปัดแต่ละลูกจะถูกย้ายทีละลูก นี่เป็นกรณี่จัดเรียงแบบลูกปัดโดยไม่มีกลไกเพื่อช่วยในการหาช่องว่างด้านล่างของลูกปัด

ตัวอย่างการเขียนโปรแกรม

ตัวอย่างการเขียนโปรแกรมด้วยภาษาไพทอน (Python) โปรแกรมนี้ใช้ได้เฉพาะกับชุดข้อมูลที่มีสมาชิกภายในเป็น จำนวนเต็มบวก หรือ มากกว่า 0

def Gravity(obj):  n = len(obj)  if all([type(x) == int and x >= 0 for x in obj]):  reference = [range(x) for x in obj]  else:  raise ValueError("All elements must be positive integers")   intermediate = []  index = 0  previous = n   while previous:  intermediate.append(range(previous))  index += 1  previous = sum([1 for x in reference if len(x) > index])   index = 0  previous = len(intermediate)] # จำนวนที่มากที่สุด  out = [0 for x in range(n)]  out[n-1] = previous  # แปลงเป็นชุดข้อมูลแบบตัวเลข  for i in range(0,n-1):  previous = sum([1 for x in intermediate if len(x) > n-i-1])  out[i] = previous   return out  obj = [2, 4, 1, 3, 3] print(Gravity(obj)) # [1, 2, 3, 3, 4] 

อ้างอิง

kukuruku. Bead Sort. Retrieved 5 may 2018