1. How many sub arrays does the quick sort algorithm divide the entire array into?
a) one
b) two
c) three
d) four
Explanation: The entire array is divided into two partitions, 1st sub array containing elements less than the pivot element and 2nd sub array containing elements greater than the pivot element.
2. Which is the worst method of choosing a pivot element?
a) first element as pivot
b) last element as pivot
c) median-of-three partitioning
d) random element as pivot
Explanation: Choosing the first element as pivot is the worst method because if the input is pre-sorted or in reverse order, then the pivot provides a poor partition.
3. Which among the following is the best cut-off range to perform insertion sort within a quick sort?
a) N=0-5
b) N=5-20
c) N=20-30
d) N>30
Explanation: A good cut-off range is anywhere between N=5 and N=20 to avoid nasty degenerate cases.
4. Quick sort is a __________
a) greedy algorithm
b) divide and conquer algorithm
c) dynamic programming algorithm
d) backtracking algorithm
Explanation: Quick sort is a divide and conquer algorithm. Quick sort first partitions a large array into two smaller sub-arrays. And then recursively sorts the sub-arrays.
5. What is the worst case time complexity of the Quick sort?
a) O(nlogn)
b) O(n)
c) O(n3)
d) O(n2)
Explanation: The worst case running time for Quick sort is O(n2). In Quick sort, the worst case behaviour occurs when the partitioning routine produces two sub-arrays one with n – 1 element and other with 0 elements.
6. Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after first phase, pivot is first element?
a) 6 4 3 7 11 9 14 12
b) 6 3 4 7 9 14 11 12
c) 7 6 14 11 9 4 3 12
d) 7 6 4 3 9 14 11 12
Explanation: Let’s apply Quick sort on the given sequence,
For first phase, pivot = 7
7 11 14 6 9 4 3 12
i j
7 11 14 6 9 4 3 12
i j
7 3 14 6 9 4 11 12
i j
7 3 4 6 9 14 11 12
i j
7 3 4 6 9 14 11 12
j i
6 3 4 7 9 14 11 12
7. The best case behaviour occurs for quick sort is, if partition splits the array of size n into __________
a) n/2 : (n/2) – 1
b) n/2 : n/3
c) n/4 : 3n/2
d) n/4 : 3n/4
Explanation: The best case analysis of quick sort occurs when the partition splits the array into two subarrays, each of size no more than n/2 since one is of size n/2 and one of size (n/2) – 1.
8. Quick sort is a stable sorting algorithm.
a) True
b) False
Explanation: In stable sorting algorithm the records with equal keys appear in the same order in the sorted sequence as they appear in the input unsorted sequence. Quick sort does not preserve the relative order of equal sort items. Therefore, Quick sort is not a stable sort.
9. Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then T(n)<=?
a) T(n) <= 2 T(n/4) + cn
b) T(n) <= T(n/4) + T(3n/4) + cn
c) T(n) <= 2 T(3n/4) + cn
d) T(n) <= T(n/3) + T(3n/4) + cn
Explanation: If there are n/4 elements in one sub-array then T(n/4) comparisons are needed for this sub-array. And T(3n/4) comparison are required for the rest 4n/5 elements, and cn is time required for finding the pivot. If there are more than n/4 elements in one sub-array then other sub-array will have less than 3n/4 elements and time complexity will be less than T(n/4) + T(3n/4) + cn.
10. Consider the Quick sort algorithm which sorts elements in ascending order using the first element as pivot. Then which of the following input sequence will require a maximum number of comparisons when this algorithm is applied on it?
a) 22 25 56 67 89
b) 52 25 76 67 89
c) 22 25 76 67 50
d) 52 25 89 67 76
Explanation: If the input sequence is already sorted then worst case behaviour occurs for the Quick sort algorithm which use the first element as pivot. Therefore, the input sequence given in 22 25 56 67 89 will require a maximum number of comparisons.
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.