ผู้ใช้:กิตติสรณ์ อภัยจิตร์/กระบะทราย

รายการโยงวน หรือ รายการโยงวงกลม (อังกฤษ: Circularly linked list) เป็น รายการโยง (link list) ชนิดหนึ่ง โดยที่เชื่อมโยงข้อมูลจากตัวแรกไปยังข้อมูลถัดไปที่เชื่อมโยงกันอยู่ต่อไปเรื่อยๆจนถึงข้อมูลตัวที่เพิ่มเข้ามาล่าสุด และจะเชื่อมโยงไปยังข้อมูลตัวแรกของชุดข้อมูลชุดเดียวกัน ซึ่งเป็นลักษณะเฉพาะของรายการโยงนี้

การเพิ่มข้อมูล

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

การแสดงข้อมูลจากรายการโยงวน

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

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

ความซับซ้อนของการทำงานนั้นจะขึ้นอยู่กับขนาดของข้อมูลทั้งหมดของชุดข้อมูล ดังนั้นสรุปได้ว่า Big(o) = O(n) ซึ่ง n คือ จำนวนข้อมูลทั้งหมด

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

ตัวอย่างการเขียนโปรแกรมด้วยภาษาไพทอน (Python)

class Node:
     
    # โครงสร้างของโหนด
    def __init__(self, data):
        self.data = data 
        self.next = None
 
class CircularLinkedList:
     
    # สร้างชุดข้อมูลของรายการโยงวน
    def __init__(self):
        self.head = None
 
    # การเพิ่มข้อมูลเข้าในรายการโยงวน
    def push(self, data):
        ptr1 = Node(data)
        temp = self.head
         
        ptr1.next = self.head
 
        if self.head is not None:
            while(temp.next != self.head):
                temp = temp.next
            temp.next = ptr1

        # กรณีรายการโยงวนยังไม่มีข้อมูล ให้โหนดที่เพิ่มเข้าเป็นโหนดเริ่มต้น
        else:          
            ptr1.next = ptr1 
            self.head = ptr1
 
    # การแสดงข้อมูลในรายการโยงวน
    def printList(self):
        show = "head "
        temp = self.head
        show += str(temp.data)
        if self.head is not None:
            while(temp.next != self.head):               
                temp = temp.next
                show += " -> " + str(temp.data)
        show += " -> head"
        return show        
 
# สร้างรายการโยงวน 
cllist = CircularLinkedList()

cllist.push(59)
cllist.push(36)
cllist.push(17)
cllist.push(3)
cllist.push(41)
 
# แสดงผลออกมาเป็น head 59 -> 36 -> 17 -> 3 -> 41 -> head
print(cllist.printList())

อ้างอิง

geeksforgeeks. Circular Linked List | Set 2 (Traversal). Retrieved 5 may 2018

==================================================================================================

การจัดเรียงแบบลูกปัด หรือที่เรียกอีกชื่อว่า การจัดเรียงแรงโน้มถ่วง เป็นขั้นตอนวิธีการเรียงลำดับแบบธรรมชาติ พัฒนาโดย 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, 10, 4, 5, 8, 9]
print(Gravity(obj)) # [2, 4, 5, 8, 9, 10]

อ้างอิง

kukuruku. Bead Sort. Retrieved 5 may 2018

en.wikipedia. Bead sort. Retrieved 5 may 2018