Bissoy.com
Doctors Medicines MCQs Q&A

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.

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. Correct Answer 10, 20, 50, 30, 40

The correct answer is option 2.

Concept:

QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

  • Always pick the first element as a pivot.
  • Always pick the last element as the pivot.
  • Pick a random element as a pivot.
  • Pick median as the pivot.

Here given, Assume that there is a divide and conquer quick sort algorithm and in the partition algorithm, the first element of the lists is taken as pivot-element.

Option 1: 40, 50, 10, 20, 30

False, Here the pivot element is 40. After running quick sort the sequence will be like 20, 50, 10, 40, 30. So the given sequence of the numbers X2,5 = 1 is not correct.

Option 2: 10, 20, 50, 30, 40

True, Here the pivot element is 10. After running quick sort the sequence will be like 10, 20, 50, 30, 40. So the given sequence of the numbers X2,5 = 1 is the correct sequence.

After the pivot is 20, it divides the sequence like 10, 20, 50, 30, 40. And X3,5 = 1

After the pivot is 50, it divides the sequence like 10, 20, 40, 30, 50.  And X4,5 = 1. So on.

Option 3: 40, 20, 10, 30, 50

False, Here the pivot element is 40. After running quick sort the sequence will be like 30, 20, 10, 40, 50. So the given sequence of the numbers X2,5 = 1 is not correct.

Option 4: 30, 20, 10, 40, 50

False, Here the pivot element is 30. After running quick sort the sequence will be like 10, 20, 30, 40, 50. So the given sequence of the numbers X2,5 = 1 is not correct.

Hence the correct answer is 10, 20, 50, 30, 40.

Additional InformationQuicksort:

The worst-case time complexity quicksort algorithm is O(n2) if the array is sorted.
T(n) = T(n-1) + cn

That's why randomized quick sort come to make time complexity O(N log N)
Randomized quicksort:
Randomized quicksort says instead of picking the pivot to be the first element what if pick my pivot to be a random element from my array A.

Related Questions

Propositions are
1. A son is liable, before partition, for the debts contracted by his father before partition which are not immoral or illegal.
2. A son is liable, after partition, for the debts contracted by his father before partition which are not immoral or illegal.
3. A son is liable, after partition, for the debts contracted by his father after partition which are not immoral or illegal which of the following is true in respect of the aforesaid propositions.
Consider the global matrix AΦ=b. Let the coefficient matrix A=M-N. At the ith iteration, the general form can be given as ______________ (Note: Φi is the value of Φ in the ith iteration).
Consider the global matrix AΦ=b. What is the residual at the ith iteration? (Note: Φi is the value of Φ in the ith iteration).
In a suit for partition of property and for separate possession of a share therein, the civil court having declared the rights of several parties interested in the property:
1. Which is assessed to payment of revenue to the Government, must make over the matter for such partition or separation to be made by the Collector.
2. Which is not so assessed to payment of revenue to the Government, must examine if the partition or separation can be conveniently made and for this, may issue a Commission to make the partition or separation.
3. If on examination of the report of the Commissioner, the Court finds that the property cannot be divided by metes and bounds, it may put it to sale and divide the proceeds thereof.
In the above:
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
Given below are some famous algorithms and some algorithm design paradigms Algorithms Design Paradigm  1. Dijkstra's shortest path algorithms  (a) Greedy design  2. Floyd-Warshall's all-pair-shortest path algorithms  (b) Divide and conquer  3. Kruskal's minimum spanning tree algorithm  (c) Dynamic programming  4. Merge Sort algorithm     Which of the following correspondence is correct?
There are two rows, each containing 3 numbers. Some rules are given below to be used for obtaining the resultant number for each row separately. Apply the rules for each row from left to right and answer the question. Rules: i. If an even number is followed by an even number, the first is to be subtracted from the second. ii. If an odd number is followed by an odd number, both are to be added. iii. If an odd number is followed by an even number, the even number is to be subtracted from the square of the odd number. iv. If an even number is followed by an odd number, the odd number is to be subtracted from the even number. Row I: 28, 19, 12 Row II: 13, 7, 32 What is the average of the resultant numbers of the first row and the second row?
The given question consists of three statements numbered I, II and III. You have to decide whether the data provided in the statements are sufficient to answer the question. Read all the statements and answer the question. What will be the sum of two numbers? I. Among the two numbers, the largest number is greater than the smallest number by 4. II. 30% of the smallest number is equal to 20% of the largest number. III. The ratio between half of the largest number and one fourth of the smallest number is 3 ∶ 2.
Which of the following statements are true? i) practical application of XOR linked lists are in environments with limited space requirements, such as embedded devices. ii)xor lists are not suitable because most garbage collectors will fail to work properly with classes or structures that don’t contain literal pointers iii)in order to calculate the address of the next node you need to remember the address of the previous node iv)xor lists are much efficient than single, doubly linked lists and arrays
In a survey of 25 students, it was found that 15 had taken Mathematics, 12 had taken Physics and 11 had taken Chemistry, 5 had taken Mathematics and Chemistry, 9 had taken Mathematics and Physics, 4 had taken Physics and Chemistry and 3 had taken all the three subjects. Find the number of students who had taken both Physics and Chemistry but not Mathematics.