1. Choose the correct statement about bottom up merge sort from the following?
a) bottom up merge sort has greater time complexity than standard merge sort
b) bottom up merge sort has lesser time complexity than standard merge sort
c) bottom up merge sort saves auxiliary space required on call stack
d) bottom up merge sort uses recursion.
Explanation: Bottom up merge sort unlike standard merge sort uses an iterative algorithm for sorting. Thus, it saves auxiliary space required by the call stack.
2. Which of the following sorting algorithms is the fastest?
a) Merge sort
b) Quick sort
c) Insertion sort
d) Shell sort
Explanation: Quick sort is the fastest known sorting algorithm because of its highly optimized inner loop.
3. Quick sort follows Divide-and-Conquer strategy.
a) True
b) False
Explanation: In quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer strategy).
4. What is the worst case time complexity of a quick sort algorithm?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
Explanation: The worst case performance of a quick sort algorithm is mathematically found to be O(N2).
5. Which of the following methods is the most effective for picking the pivot element?
a) first element
b) last element
c) median-of-three partitioning
d) random element
Explanation: Median-of-three partitioning is the best method for choosing an appropriate pivot element. Picking a first, last or random element as a pivot is not much effective.
6. Find the pivot element from the given input using median-of-three partitioning method.
8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
a) 8
b) 7
c) 9
d) 6
Explanation: Left element=8, right element=0,
Centre=[position(left+right)/2]=6.
7. Which is the safest method to choose a pivot element?
a) choosing a random element as pivot
b) choosing the first element as pivot
c) choosing the last element as pivot
d) median-of-three partitioning method
Explanation: This is the safest method to choose the pivot element since it is very unlikely that a random pivot would consistently provide a poor partition.
8. What is the average running time of a quick sort algorithm?
a) O(N2)
b) O(N)
c) O(N log N)
d) O(log N)
Explanation: The best case and average case analysis of a quick sort algorithm are mathematically found to be O(N log N).
9. Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
a) Merge sort
b) Shell sort
c) Insertion sort
d) Bubble sort
Explanation: Insertion sort is used along with quick sort to sort the sub arrays.
It is used only at the end.
10. Quick sort uses join operation rather than merge operation.
a) true
b) false
Explanation: Quick sort uses join operation since join is a faster operation than merge.
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.