Sorting Algorithms Questions and Answers

Q: Suppose that the splits at every level of quicksort are in the proportion \((1 - \alpha)\) to \(\alpha\), where \(0 \lt \alpha \le \frac{1}{2}\) is a constant. The minimum depth of a leaf in the recursion tree is approximately given by

The minimum depth is \(-\lg n / \lg \alpha\).The shallowest path always follows the smaller part \(\alpha\) of each split. After \(k\) levels the subproblem has size \(\alpha^{k} n\) and the leaf is reached when \(\alpha^{k} n = 1\), giving \[ k = -\frac{\lg n}{\lg \alpha}. \]The expression with \(\lg(1 - \alpha)\) is the maximum depth, which follows the larger part, and the expressions with \(\lg n\) in the denominator are not depths.

21.

Mergesort makes two recursive calls. Which statement is true after these two recursive calls finish, but before the merge step ?

A.The array elements form a heap.
B.Elements in each half of the array are sorted amongst themselves.
C.Elements in the first half of the array are less than or equal to elements in second half of the array.
D.All of the above

Exam Year(s)

UGC NET - 2014,

Answer: B

After the two recursive calls and before the merge, the elements in each half of the array are sorted among themselves. Mergesort sorts the left half and the right half separately and then merges them, so at this point each half is in order, but there is no relation between the halves, so the first half need not be smaller than the second and the array does not form a heap. The statement that all of them hold is therefore false. The merge step then combines the two sorted halves into one, and it is only after that step that the whole array is in order.

Discuss in Forum

22.

Suppose that the splits at every level of quicksort are in the proportion \((1 - \alpha)\) to \(\alpha\), where \(0 \lt \alpha \le \frac{1}{2}\) is a constant. The minimum depth of a leaf in the recursion tree is approximately given by

A.\(-\frac{\lg n}{\lg(1 - \alpha)}\)
B.\(-\frac{\lg(1 - \alpha)}{\lg n}\)
C.\(-\frac{\lg n}{\lg \alpha}\)
D.\(-\frac{\lg \alpha}{\lg n}\)

Exam Year(s)

UGC NET - 2014,

Answer: C

The minimum depth is \(-\lg n / \lg \alpha\).

The shallowest path always follows the smaller part \(\alpha\) of each split. After \(k\) levels the subproblem has size \(\alpha^{k} n\) and the leaf is reached when \(\alpha^{k} n = 1\), giving \[ k = -\frac{\lg n}{\lg \alpha}. \]

The expression with \(\lg(1 - \alpha)\) is the maximum depth, which follows the larger part, and the expressions with \(\lg n\) in the denominator are not depths.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Sorting Algorithms Questions and Answers || Sorting Algorithms MCQ Questions and Answers || Sorting Algorithms GK Questions and Answers || Sorting Algorithms GK MCQ Questions || Sorting Algorithms Multiple Choice Questions and Answers || Sorting Algorithms GK || GK on Sorting Algorithms || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Sorting Algorithms Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications