บทนำ
Circular Linked List คือ linked list ที่ tail ชี้กลับไปที่ head วนเป็นวงกลม การเรียงลำดับ (Sort) สามารถทำได้ด้วย Bubble Sort แบบปรับเปลี่ยนสำหรับโครงสร้างวงกลม
โค้ดตัวอย่าง
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = self.head
else:
curr = self.head
while curr.next != self.head:
curr = curr.next
curr.next = new_node
new_node.next = self.head
def sort_list(self):
"""Bubble sort สำหรับ circular linked list"""
if self.head is None:
return
swapped = True
while swapped:
swapped = False
curr = self.head
while curr.next != self.head:
if curr.data > curr.next.data:
# สลับ data
curr.data, curr.next.data = curr.next.data, curr.data
swapped = True
curr = curr.next
def display(self):
if self.head is None:
print("ลิสต์ว่าง")
return
curr = self.head
while True:
print(curr.data, end=' ')
curr = curr.next
if curr == self.head:
break
print()
# ทดสอบ
cll = CircularLinkedList()
for v in [21, 54, 78, 99, 27]:
cll.append(v)
print("ก่อนเรียง:", end=' ')
cll.display()
cll.sort_list()
print("หลังเรียง:", end=' ')
cll.display()
ผลลัพธ์
ก่อนเรียง: 21 54 78 99 27 หลังเรียง: 21 27 54 78 99
คำอธิบาย
- Circular list:
curr.next == headคือจบรอบ - Bubble sort: เปรียบเทียบ adjacent nodes สลับ data ถ้าผิดลำดับ
swappedflag ตรวจสอบว่ามีการสลับในรอบนั้นหรือไม่- สลับ data โดยตรง (ไม่สลับ node) ง่ายกว่า
ความซับซ้อน
- เวลา: O(n²) - Bubble sort
- พื้นที่: O(1)
- สำหรับข้อมูลมาก ควรแปลงเป็นลิสต์ เรียง แล้วสร้าง circular list ใหม่ (O(n log n))
การปรับปรุง: Merge Sort
สำหรับ linked list Merge Sort เหมาะกว่า (O(n log n), stable) แต่ซับซ้อนกว่า ต้องหาจุดกลางด้วย slow/fast pointer แล้ว split และ merge
