Test: Divide & Conquer- 1 - Computer Science Engineering (CSE) MCQ

It is done only by insertion sort because in insertion sort we compare the one card to another all inserted card.

if we want to check if given input is sort or not then one pass of bubble sort and n pass of insertion sort with each has work of O(1) are best i.e.take O(n) time.

If number of swapping is the measure of efficiency of algorithm the selection sort is best since it cannot take swap more than O(n).

In-order traversal of a Binary Search Tree lists the nodes in ascending order.

Rearranging the library books in a shelf in proper order is same as arranging cards. So insertion sort should be preferred.

Binary insertion sort take minimum comparison if the list to be sorted is in reverse order and maximum number of comparison if they already in sorted order.

Quick sort has two worst cases, when input is in either ascending or descending order, it takes same time O(n²).

Quick sort algorithm uses divide and conquer technique. It divides the data set every time on pivot element and keep on sorting each data set recursively.

Preorder is root, left, right.

• So, option (b) can’t be a valid output. Since, 5 being the root and [312] a left sub-tree and [6487] being a right sub tree. But, 4 < 5, so not possible.
• In option (a), considering 5 as root, [786] becomes the right sub tree. Further, 7 being the root 6 can’t be apart of right sub-tree.
• Similarly, we can shown (c) can’t be a valid output.
• So, (d) can be the only possible valid output.

The shell sort sometimes called the “diminishing increment sort" improves on the insertion sort by breaking the original list into a number of smaller sub list each of which is sorted using an insertion sort.