This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Sleep Sort”.
1. Which of the following header file is a must to implement sleep sort algorithm?
a) string.h
b) math.hw
c) bios.h
d) windows.h
View Answer
Explanation: To implement sleep sort algorithm we need functions like WaitForMultipleObjects(), _beginthread(). These are included in the header file windows.h.
2. Sleep sort does not work for ___________
a) negative numbers
b) large numbers
c) small numbers
d) positive numbers
View Answer
Explanation: Sleep sort algorithm does not work for negative numbers. It is because thread cannot sleep for negative amount of time.
3. In how many comparisons does the array arr={1,4,2,3,5} gets sorted if we use sleep sort?
a) 5
b) 3
c) 1
d) 0
View Answer
Explanation: 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.
4. Sleep sort works by ___________
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
View Answer
Explanation: 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.
5. Sleep sort code cannot compile online because ___________
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
View Answer
Explanation: 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.
6. Time complexity of sleep sort can be approximated to be ___________
a) O(n + max(input))
b) O(n2)
c) O(n log n + max(input))
d) O(n log n)
View Answer
Explanation: 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)).
7. Sleep sort can be preferred over which of the following sorting algorithms for large number of input elements?
a) Quick sort
b) Bubble sort
c) Selection sort
d) No sorting algorithm is preferred
View Answer
Explanation: 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.
8. Auxiliary space requirement of sleep sort is ___________
a) O(n)
b) O(1)
c) O(max(input))
d) O(log n)
View Answer
Explanation: 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.
9. Sleep sort does gives a correct output when ___________
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
View Answer
Explanation: 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.
10. Which of the following sorting algorithm is most closely related to the OS?
a) gnome sort
b) sleep sort
c) radix sort
d) bogo sort
View Answer
Explanation: 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.
11. Sleep sort is an in-place sorting technique.
a) True
b) False
View Answer
Explanation: 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.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Data Structure MCQ
- Check Programming Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Practice Programming MCQs