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

การจัดเรียงแบบลูกปัด หรือที่เรียกอีกชื่อว่า การจัดเรียงแบบแรงโน้มถ่วง เป็นขั้นตอนวิธีการเรียงลำดับแบบธรรมชาติ พัฒนาโดย 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