1. A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. The minimum time needed to sort 200 elements will be approximately __________
a) 60.2 sec
b) 45.54 sec
c) 31.11 sec
d) 20 sec
Explanation: The Quick sort requires nlog2n comparisons in best case, where n is size of input array. So, 1000 * log21000 ≈ 9000 comparisons are required to sort 1000 elements, which takes 200 sec. To sort 200 elements minimum of 200 * log2200 ≈ 1400 comparisons are required. This will take 200 * 1400 / 9000 ≈ 31.11 sec.
2. Which one of the following sorting algorithm is best suited to sort an array of 1 million elements?
a) Bubble sort
b) Insertion sort
c) Merge sort
d) Quick sort
Explanation: The Quick sort is best suited to sort the array of 1 million elements. The practical implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely shows worst case behaviour and is almost always O(nlogn). And Quick sort requires little additional space and exhibits good cache locality.
3. Quick sort is a space-optimised version of ____
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Binary tree sort
Explanation: Quick sort is a space-optimised version of the binary tree sort. In binary sort tree, the elements are inserted sequentially into the binary search tree and Quick sort organises elements into a tree that is implied by the recursive calls.
4. Quick sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Explanation: Quick sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two parts about the pivot and then apply a quick sort to both the parts.
5. What is a randomized quick sort?
a) quick sort with random partitions
b) quick sort with random choice of pivot
c) quick sort with random output
d) quick sort with random input
Explanation: Randomized quick sort chooses a random element as a pivot. It is done so as to avoid the worst case of quick sort in which the input array is already sorted.
6. What is the purpose of using randomized quick sort over standard quick sort?
a) so as to avoid worst case time complexity
b) so as to avoid worst case space complexity
c) to improve accuracy of output
d) to improve average case time complexity
Explanation: Randomized quick sort helps in avoiding the worst case time complexity of O(n2) which occurs in case when the input array is already sorted. However the average case and best case time complexities remain unaltered.
7. What is the auxiliary space complexity of randomized quick sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Explanation: Auxiliary space complexity of randomized quick sort is O(log n) which is used for storing call stack formed due to recursion. Note that the algorithms with space complexity as O(log n) also qualifies as in place algorithms as the value of log n is close to 1.
8. What is the average time complexity of randomized quick sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Explanation: The average case time complexity of randomized quick sort is same as that of standard quick sort as randomized quick sort only helps in preventing the worst case. It is equal to O(n log n).
9. Quick sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
Explanation: Quick sort makes partitions of the input array about the pivot in order to implement sorting. Thus its method of sorting is called partitioning.
10. Randomized quick sort is an in place sort.
a) true
b) false
Explanation: In-place algorithms requires constant or very less auxiliary space. Quick sort qualifies as an in place sorting algorithm as it has a very low auxiliary space requirement of O(log n).
Design and Analysis of Algorithms
The Prelude: What's Quicksort All About?
Imagine you're hosting a fabulous dinner party and want to arrange your guests in ascending order of height. Quicksort is your suave choreographer, orchestrating the perfect sorting performance. The algorithm picks a 'pivot' guest, making sure taller guests stand on one side, shorter on the other.
The Dance Begins: Partitioning and Conquering
In the first dance move, Quicksort partitions the guests around the pivot, akin to separating the waltzing couples. The beauty lies in its efficiency—dividing and conquering like a maestro, swiftly organizing the party-goers into height-sorted harmony.
The Pivot Shuffle: A Clever Strategy
Picture the pivot as the lead dancer—it strategically selects partners (elements) for the dance, ensuring a well-balanced performance. This clever choice minimizes the number of moves, making Quicksort a headliner in the sorting spectacle.
A Show of Agility: Best and Average-Case Performance
Quicksort's nimbleness on the dance floor isn't just for show. In the best-case scenario, when the pivot always picks the median, the algorithm exhibits O(n log n) brilliance. Even in the average case, it dazzles with its swift moves, outperforming many counterparts.
As the curtains fall, let's compare Quicksort to its rivals. Its adaptive nature and elegance set it apart, making it a star performer in the Design and Analysis of Algorithms gala.