Algorithms Consider the following stratetgy for choosing a pivot element for the

ID: 3871007 • Letter: A

Question

Algorithms

Consider the following stratetgy for choosing a pivot element for the Partition subroutine of wquickSort, applied to an array A.

1) Let n be the number of elements of the array A.

2) If n >=15, perform an insertion Sort of A and return.

3) Otherwise:

--- Choose 2[sqrt(n)] elements at random from n; let S be the new list with the chose elements.

--- Sort the list S using Insertio nSort and use the median m of S as a pivot element

--- Partition using m as a pivot

--- Carry out QuickSort recusively on the two parts.

(a) If the element m obtained as the median of S is used as the pivot, what can we say about the sizes of the two partitions of the array A?

(Please show detailed work, Thank you. )

PART B&C OF THIS PROBLEM IS POSTED ON ANOTHER THREAD.

THE ELEMENTS WILL BE DIVIDED INTO TWO EQUAL HALVES(IN MAJORITY OF THE CASES).

THE REASON BEING IS WE ARE CHOOSING SOME ELEMENTS FROM THE LIST RANDOMLY AND ATMOST THEY WILL BE 7 (2*SQRT(N))

THEN WE ARE SORTING THEM AND FINDING THE MEDIAN. HERE MEDIAN WILL BE THE MIDDLE ELEMENT.

eg- Let the list ne 5,2,3,4,6,8,7,9,10

Here we are taking n elements to be 9

hence sqrt(9) is 3

so we have to select 6 elements as 2,3,4,6,7,8

the median is 6.

Hence it will be into two hlves

HENCE WE HAVE FOUND OUT THAT IT WILL BE PIVOT AND IN MAJOR CASES IT WILL BE EASY TO DIVIDE INTO TWO PARTS.

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