1. Which of the following algorithm is implemented internally in java when we use function arrays.sort()?
a) intro sort
b) quick sort
c) tim sort
d) merge sort
Explanation: Java makes use of Tim sort internally for implementing arrays.sort(). It is mainly due to the fastness of this algorithm in comparison to other comparison based sorts.
2. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for Tim sort implementation?
a) Because insertion sort is faster and adaptive
b) Because insertion sort requires less space
c) Because insertion sort is easy to implement
d) Because insertion sort is easy to understand
Explanation: When small arrays need to be sorted then insertion sort proves to be the best choice. Also, it is adaptive so it performs better than others when the given array is fully/partially sorted.
3. In which case will tim sort will work as an insertion sort?
a) when no. of elements are less than 64
b) when no. of elements are greater than 64
c) when no. of elements are less than size of run
d) when no. of elements are less than 32
Explanation: Tim sort uses a hybrid of insertion and merge sort. It reduces to insertion sort when the size of array is less than the size of run as insertion sort is efficient in sorting small arrays.
4. What is the usual size of a run in tim sort?
a) 32
b) less than 32
c) 32-64 depending on size of the array
d) 64
Explanation: Usually the size of the run is chosen somewhere between 32 and 64. The size of run is preferably chosen in powers of 2 in order to maintain balance while merging the sorted runs.
5. Which of the following is an example of parallel sorting technique?
a) bogo sort
b) sleep sort
c) cube sort
d) merge sort
Explanation: Out of the given options only cube sort is a parallel sorting algorithm. It builds self balancing multi dimensional arrays from the input keys.
6. What is the auxiliary space requirement of cube sort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)
Explanation: Cube sort requires an auxiliary space of O(n). This is the worst case of auxiliary space complexity.
7. What is the best case time complexity of cube sort?
a) O(n2)
b) O(n)
c) O(n log n)
d) O(1)
Explanation: Best case time complexity of cube sort occurs when the input array is almost sorted. So in such a case only O(n) time is required for sorting.
8. What is the average case time complexity of cube sort?
a) O(n2)
b) O(n log n)
c) O(log n)
d) O(n)
Explanation: The average case performance of cube sort is O(n log n). This is the fastest possible complexity with a comparison based sort.
9. Which of the following algorithm is stable?
a) heap sort
b) cube sort
c) quick sort
d) bogosort
Explanation: Out of the given algorithms only cube sort is stable. This implies that the relative position of equal valued elements in the input and sorted array remains the same.
10. Cube sort is a comparison based sort.
a) true
b) false
Explanation: Cube sort is a comparison based sorting algorithm. This is because it compares elements in order to sort them.
Design and Analysis of Algorithms
Cubing the Chaos: A Brief Introduction
Ever wondered how your computer effortlessly sorts through a gazillion numbers? Well, meet Cubesort – the unsung hero of sorting algorithms. Unlike its traditional counterparts, Cubesort adds a dash of spice by sorting in three dimensions. Imagine a Rubik's Cube, but instead of colors, we're juggling numbers!
Dance of the Cubes: How It Works
A dance floor filled with cubes, each representing a number. Cubesort grooves through them, swapping, twirling, and shimmying until they fall into a perfect, sorted formation. It's like a dance competition where every move counts, and the result is a synchronized symphony of numbers.
Why Choose Cubesort in Your Algorithm Playlist?
1. Efficiency Unleashed: Cubesort struts its stuff by leveraging parallel processing, making it a speed demon in sorting large datasets.
2. Spatial Prowess: Embracing the third dimension allows Cubesort to outshine 2D algorithms, showcasing its spatial prowess like a magician pulling rabbits out of hats.
3. Algorithmic Elegance: Cubesort isn't just a jumble of moves. It's a choreographed ballet, demonstrating elegance in algorithmic design.
Feel the algorithmic vibes, embrace the Cubesort charm, and let the sorting adventure begin! Algorithm aficionados, stay tuned for more algorithmic wonders – because in the world of code, every line tells a story.