Question

1. If we view the selection sort as an application of "divide and conquer"

strategy, what is the two-part partitioning of the index range [0, n)? Is it a balanced partition?

2. For the "divide and conquer" strategy for developing algorithm, do we pursue

balanced partitioning or unbalanced partitioning? Why?

3. For the quicksort, the selection of pivot determines the quality of partitioning.

Do we have any easy or cheap way for selecting a good pivot that always leads

to a very balanced partition?

Answer 1

1.If we see selection sort as application of divide and conquer strategey then in this the two divisions are sucth that first section includes larger element and other section includes n-1 elements.

This partitioning is not balanced partitioning as in balaced partioitoning there is an equal division or we can say that division takes place such that the algorithm runs asymtotically fast but in this division takes place like n-1,n-2 and so on.

2.We prefer balanced partitioning over unbalanced partitioning for divide and conquer starategy as if the partitioning is balanced, the algorithm runs asymptotically as fast as merge sort. If the partitioning is unbalanced, however, it can run asymptotically as slow as insertion sort.

3.If we want balanced partitioning in quick sort then pivot element should be the middle element i.e in every partiotion pivot element lies in middle.This will lead to partition such as n-1/2.

I hope my answer met all your requirements.

THANKYOU!