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 |
O(n²+max(input)) | |
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]
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
Sleep Sort epnxlkxrithumkareriyngladbtamewla thanganodyechuxmoyngtwnbewlakbaetlaixethmthitxngkarcaeriyngladb ekhanetxraetlatwcatngkhaerimtndwykhakhxngxngkhprakxbthicasng ekhanetxrcaldlng aelwthikhwamerwethakn emuxtwnbthikahndsinsudlngxngkhprakxbthiechuxmoyngcathukephimlngintxnthaykhxngraykar enuxngcaktwnbhyudkhunxyukbkhnadkhxngxngkhprakxbraykarcaeriyngladbemuxekhanetxrthnghmdthukhyudlng samarthichnganidodyichtwcbewlarabbptibtikarechnodykaraeykaetlakrabwnkarxxkepnswn hruxichewkhetxrtwnbprasiththiphaphsleep sort cakxihekidkrabwnkarhnungsahrbaetlaxarkiwemnt aetlakrabwnkarrxpraman n winathicaknnphimph n xxkma sunghmaykhwamwaichewla 1 winathiinkarphimph 1 2 winathiephuxphimph 2 100 winathiephuxphimph 100 sunghmaykhwamwaswnihytwelkhcathukphimphxxkmatamladbkhnadkhxngmndngnncungepnkar eriyngladb xarkiwemnt khwamsbsxnkhxngxlkxrithumniinolkthismburnaebbkhux O max args 1 enuxngcakcaichewlasungsud args winathiinkarphimph arg thikhnadihythisud inkhwamepncringkhwamsbsxnkhux O n 2 max args 2 enuxngcakkarrksakrabwnkarphunhlnghlayrabbkhunxyukbrabbptibtikarephuxcdkarkarslbbribthaelacdladbkhwamsakhykhxngkrabwnkardngnnxlkxrithumcungichkarcderiyngthiaethcringkhxngekhxrenl nxkcakniyngimmikarkhapraknwaphllphthkhxngkarcderiyngepncringthuktxngsungepnkhunlksnathixlkxrithumkareriyngladbxunswnihyimmiClass Sorting AlgorithmData Structure ArrayO n max input O max input CodingPython 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 lt 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