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

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

ประสิทธิภาพ

sleep sort จะก่อให้เกิดกระบวนการหนึ่งสำหรับแต่ละอาร์กิวเมนต์ แต่ละกระบวนการรอประมาณ n วินาทีจากนั้นพิมพ์ n ออกมา ซึ่งหมายความว่าใช้เวลา 1 วินาทีในการพิมพ์ "1", 2 วินาทีเพื่อพิมพ์ "2", 100 วินาทีเพื่อพิมพ์ "100" ซึ่งหมายความว่าส่วนใหญ่ตัวเลขจะถูกพิมพ์ออกมาตามลำดับขนาดของมันดังนั้นจึงเป็นการ "เรียงลำดับ" อาร์กิวเมนต์

ความซับซ้อนของอัลกอริธึมนี้ในโลกที่สมบูรณ์แบบคือ O (max (args))[1] เนื่องจากจะใช้เวลาสูงสุด (args) วินาทีในการพิมพ์ arg ที่ขนาดใหญ่ที่สุด ในความเป็นจริงความซับซ้อนคือ O (n ^ 2 + max (args))[2] เนื่องจากการรักษากระบวนการพื้นหลังหลายระบบขึ้นอยู่กับระบบปฏิบัติการเพื่อจัดการการสลับบริบทและจัดลำดับความสำคัญของกระบวนการดังนั้นอัลกอริทึมจึงใช้การจัดเรียงที่แท้จริงของเคอร์เนล

นอกจากนี้ยังไม่มีการค้ำประกันว่าผลลัพธ์ของการจัดเรียงเป็นจริงถูกต้องซึ่งเป็นคุณลักษณะที่อัลกอริทึมการเรียงลำดับอื่นๆส่วนใหญ่ไม่มี

 

Class	Sorting Algorithm
Data Structure	Array
Worst-case performance	O(n²+max(input))
Best-case performance	O(max(input))

Coding

Python

from time import sleep from threading import Timer def sleepsort(values): sleepsort.result = [] def add1(x): s leepsort.result.append(x) mx = values[0] for v in values: if mx < v: mx = v Timer(v, add1, [v]).start() sleep(mx+1) return sleepsort.result x = [5, 1, 3, 7] print sleepsort(x) 

Result = [1, 3, 5, 7]