Bissoy.com
Doctors Medicines MCQs Q&A

Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparison made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparison made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds? Correct Answer t<sub>1</sub> &gt; t<sub>2</sub>

Concept:

If the array is sorting is increasing or non-increasing order, choosing either first or last element given the worst-case time complexity in Quick Sort.

Explanation

In every step of quick sort, numbers are divided as per the following recurrence.

T(n) = T(n-1) + O(n)

Average case time complexity (t2) = O(logn)

Worst case time complexity (t1) = O(n2)

Since t1 has the worst case ∴ t1 > t2

Important Point:

Number of comparisons will vary based on implementation

Always in ascending or descending array (worst case) number of comparisons is higher

Related Questions

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n number using randomized quicksort?
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Quicksort runs in Θ (n2) time II. Bubblesort runs in Θ (n2) time III. Mergesort runs in Θ (n) time IV. Insertion sort runs in Θ (n) time
Consider three software items: Program-X, Control Flow Diagram of Program-Y and Control Flow Diagram of Program-Z as shown below Program-X: Control Flow Diagram of Program-Y sumcal (int maxint, int value) {       int result=0, i=0;       if (value <0)       {           Value = -value;       }       while ( (i
The median for an odd number of observations is _________ where n is the number of observations. rank on the ascending order of observations b) rank on the ascending order of observations c) Average of and (n/2) rank on the ascending order of observations d) (n/2) rank on the ascending order of observations
Randomized quick sort is an extension of quicksort where the pivot is chosen randomly. what is the worst case complexity of sorting a numbers using randomized quick sort?
Let Xij =I { zi is compared to zj in quick sort algorithm} is an indicator variable, and zi is the ith smallest number. Which of the following sequence of the numbers give the X2,5 = 1? Note: Assume that there is a divide and conquer quick sort algorithm and in partition algorithm the first element of the lists is taken as pivot-element.
At an Electronic Data processing unit, five out of the eight program sets P,Q,R,S,T,U,V and W are to be operated daily. On any one day, except for the first day of a month, only three of the program sets must be the ones that were operated on the previous day. The program operating must also satisfy the following conditions: 1. If program P is to be operated on a day, V can’t be operated on that day. 2. If Q is to be operated on a day, T must be one of the programs to be operated after Q. 3. If R is to be operated on a day, V must be one of the programs to be operated after R. 4. The last program to be operated on any day must be either S or U. If the program sets R and W are to be operated on the first day, which of the following could be the other program on that day?
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?
For even number of observations of a data distribution, what is the median? rank on the ascending order of observations b) (n/2) rank on the ascending order of observations c) Average of (n/2)th observation and (n/2 + 1)th observation d) Average of and (n/2) rank on the ascending order of observations
There are two rows, each containing 3 numbers. Below are some rules to be used to get the resultant number for each row separately. Use the rule from left to right for each row and find the answer to the question. Rule: 1. If an even number is followed by an even number, then the first number will be subtracted from the second. 2. If an odd number is followed by an odd number, then both will be added. 3. If an odd number is followed by an even number, then the even number will be subtracted from the square of the odd number. 4. If an even number is followed by an odd number, then the odd number will be subtracted from the even number. Row I: 9,11, 34 Row II: 16, 9, 8 What is the difference between the resultant numbers in the first row and the second row