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

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]