sleep sort Algorithm
The Sleep Sort Algorithm is a non-traditional and unconventional sorting algorithm that applies the concept of time complexity in a unique way. It is based on the idea of creating separate threads for each element in the input array and then making each thread sleep for an amount of time corresponding to the value of the element. Once the sleeping time is over, the element is printed or added to the sorted array. The Sleep Sort Algorithm is generally not used for serious applications due to its inherent inefficiency, and it is often considered more of a creative programming exercise than a practical sorting technique.
In this algorithm, the primary focus is on the time taken by the threads to sleep rather than comparing and swapping elements, which are the usual steps involved in traditional sorting algorithms. Since the threads sleep for a time proportional to the value of the elements, the smaller elements will wake up and be printed or added to the sorted array first, followed by the larger elements. However, Sleep Sort has several limitations, such as the inability to handle negative numbers and the dependency on the underlying platform's thread scheduling and sleep precision. Additionally, it often has a higher time complexity compared to other more efficient sorting algorithms, which makes it unsuitable for use in practical applications where performance is a key requirement.
"""
Sleep sort is probably the wierdest of all sorting functions with time-complexity of
O(max(input)+n) which is quite different from almost all other sorting techniques.
If the number of inputs is small then the complexity can be approximated to be
O(max(input)) which is a constant
If the number of inputs is large, the complexity is approximately O(n).
This function uses multithreading a kind of higher order programming and calls n
functions, each with a sleep time equal to its number. Hence each of function wakes
in sorted time.
This function is not stable for very large values.
https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
"""
from threading import Timer
from time import sleep
from typing import List
def sleep_sort(values: List[int]) -> List[int]:
"""
Sort the list using sleepsort.
>>> sleep_sort([3, 2, 4, 7, 3, 6, 9, 1])
[1, 2, 3, 3, 4, 6, 7, 9]
>>> sleep_sort([3, 2, 1, 9, 8, 4, 2])
[1, 2, 2, 3, 4, 8, 9]
"""
sleep_sort.result = []
def append_to_result(x):
sleep_sort.result.append(x)
mx = values[0]
for value in values:
if mx < value:
mx = value
Timer(value, append_to_result, [value]).start()
sleep(mx + 1)
return sleep_sort.result
if __name__ == "__main__":
import doctest
doctest.testmod()
print(sleep_sort([3, 2, 4, 7, 3, 6, 9, 1]))
