In quick sort, the average case for the number of swaps is O(n log 2 n). a. true

Question

In quick sort, the average case for the number of swaps is O(n log2n).
   a. true
   b. false

In quick sort, the list is partitioned into two sublists by selecting a(n) ____, and the two sublists are then sorted and combined into one list in such a way so that the combined list is sorted.
   a. marker
   b. pivot
   c. midpoint
   d. average

It can be shown that the average number of swaps for insertion sort is ____.
   a. O(n)
   b. O(n2)
   c. O(n log n)
   d. O(n2 log n)

Merge sort divides the list into ____ sublists of nearly equal size.
   a. two
   b. three
   c. four
   d. five

Heap sort, for array-based lists, is of the order ____ even in the worst case.
   a. O(log n)
   b. O(n log n)
   c. O(log2n)
   d. O(n log2n)

Explanation / Answer

Ans 1 - False, In quick sort, the average case for the number of swaps is not O(n log2n).Its O(n log n).

Ans 2- B is the correct option ,In quick sort, the list is partitioned into two sublists by selecting a(n) Pivot, and the two sublists are then sorted and combined into one list in such a way so that the combined list is sorted.

Ans 3- It can be shown that the average number of swaps for insertion sort is O(n2).

Ans 4- A is the correct option, Merge sort divides the list into two sublists of nearly equal size.

Ans 5- B is the correct option, Heap sort, for array - based lists is of the order O(n log n) even in the worst case.

Thanks

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.