Data Structures & Algorithms Multiple Choice Questions on “Sleep Sort”.
1. Which of the following header file is a must to implement sleep sort algorithm? Answer: d 2. Sleep sort does not work for ___________ Answer: a 3. In how many comparisons does the array arr={1,4,2,3,5} gets sorted if we use sleep sort? Answer: d 4. Sleep sort works by ___________ Answer: a 5. Sleep sort code cannot compile online because ___________ Answer: c 6. Time complexity of sleep sort can be approximated to be ___________ 7. Sleep sort can be preferred over which of the following sorting algorithms for large number of input elements? 8. Auxiliary space requirement of sleep sort is ___________ 9. Sleep sort does gives a correct output when ___________ Answer: c 10. Which of the following sorting algorithm is most closely related to the OS? Answer: b 11. Sleep sort is an in-place sorting technique. Answer: a & Algorithms.
a) string.h
b) math.hw
c) bios.h
d) windows.h
Clarification: To implement sleep sort algorithm we need functions like WaitForMultipleObjects(), _beginthread(). These are included in the header file windows.h.
a) negative numbers
b) large numbers
c) small numbers
d) positive numbers
Clarification: Sleep sort algorithm does not work for negative numbers. It is because thread cannot sleep for negative amount of time.
a) 5
b) 3
c) 1
d) 0
Clarification: Sleep sort makes different elements of the array to sleep for an amount of time that is proportional to its magnitude. So it does not require to perform any comparison in order to sort the array.
a) making elements to sleep for a time that is proportional to their magnitude
b) making elements to sleep for a time that is inversely proportional to their magnitude
c) partitioning the input array
d) dividing the value of input elements
Clarification: In sleep sort each element is made to sleep for a time that is proportional to its magnitude. Then the elements are printed in the order in which they wake up.
a) it has very high time complexity
b) it has very high space complexity
c) it requires multithreading process
d) online compilers are not efficient
Clarification: Sleep sort requires multithreading process for making the elements to sleep. This process happens in the background at the core of the OS and so cannot be compiled on an online compiler.
a) O(n + max(input))
b) O(n2)
c) O(n log n + max(input))
d) O(n log n)
Answer: c
Clarification: As the sleep() function creates multiple threads by using priority queue which takes n log n time for insertion. Also the output is obtained when all the elements wake up. This time is proportional to the max(input). So its time complexity is approximately O(n log n + max(input)).
a) Quick sort
b) Bubble sort
c) Selection sort
d) No sorting algorithm is preferred
Answer: d
Clarification: Sleep sort is not preferred over any of the given sorting algorithms as sleep sort does not guarantee a correct output every time. So sleep sort is not a reliable sorting technique.
a) O(n)
b) O(1)
c) O(max(input))
d) O(log n)
Answer: b
Clarification: All the major processes involved in sleep sort takes place internally in the OS. So it does not require any auxiliary space to sort the elements.
a) any input element is negative
b) input array is reverse sorted
c) any input element is positive
d) when there is a very small number to the left of very large number
Clarification: Sleep sort gives a sorted output when the array elements are positive. But when any other case than this occur out of the above given cases then we may not see a correct output. This makes sleep sort very unreliable sorting technique.
a) gnome sort
b) sleep sort
c) radix sort
d) bogo sort
Clarification: Sleep sort is most closely related to the operating system. It is because most of the major steps of this algorithm takes place at the core of OS.
a) True
b) False
Clarification: Sleep sort is an in-place sorting technique as most of its major steps takes place in the background. So it does not require auxiliary space to sort the input.