322 views

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

i) 1,2,3,…n

ii) n,n−1,n−2,…,2,1

Let S1 and S2 be the number of swaps made for the inputs (i) and (ii) respectively. Then,

i) How is S1 and S2 related ?

ii) How will the answer change if the pivot is changed to middle element ?

| 322 views

input           :        1,2,3,4,5,6,7,8,.......n-1,n              // Elements are in increasing order , let here n=7

Algorithm    :       Quicksort                                     // PIVOT is first element

Output         :       # of Swaps                                 // Let S1

According to partition algo , if we find element (during left to right scan)less than PIVOT , onw swap needed in that case , after reaching array end , one swap with a[i] and a[L] is must (that will put PIVOT to it's right position)

Partition algo (a,i,j)  // i=index of first element , j=index of last element , a=array

{

PIVOT=a[i];   // set  first element of array as PIVOT

L=i;

for(R=i+1 , R<=j , R++)

{

if (a[R]<=PIVOT)

{    L=L+1;

Swap  (a[L] and a[R])

}

}

Swap (a[i] and a[R])      // Set PIVOT  to it's right position

Return L       // position of PIVOT

}

1 2 3 4 5 6 7      // 2≰1 , 3≰1 , 4≰1 , 5≰1 , 6≰1 , 7≰1  end came and we saw , no element found less than PIVOT so no swap during scan. but to put PIVOT to it's right place one swap is MUST

so to place 1 to it's right position , one swap is needed

when we apply same algo to remain partition , we will see that every time only one Swap is needed (to place PIVOT to it's right position) so total = n swaps  when array is in ascending order

B)

input    =     7 , 6 , 5 , 4 , 3 , 2 , 1     // elements are in descending order

Output   = # of swaps let S2

7 6 5 4 3 2 1   // L=0 run R from 1 to n-1 if found some a[R]<=PIVOT increase L

a=6 which is <=PIVOT(7) => Now L=0+1=1 and swap a to a // 1 swap

a=5 which is <= PIVOT(7) => Now L=1+1=2 and swap a to a  // 1 swap

in that way every element will get swap to itself and after reaching end , one MUST swap to set PIVOT to it's right place so total n swaps just to place 7 to it's right place , now the array would be 165432

165432 no element less than PIVOT so 0 swap but 1 must swap to place 1 to it's right position

now array is 65432 , again every element will get swap to itself => (n-2) swaps +1 (MUST swap)

so in that way (n)+1+(n-2)+1 + (n-4)+1.....which we can say O(n2) Swaps

so S1<S2

by Boss (14.4k points)
selected
0
Will the answer change if pivot elements are changed ?
0
Hello rishi , sorry for late response. Happy Diwali :)

you can easily check your second case (when pivot is middle element) using Partition algo.

You can see , what does partition algo do? it actually set PIVOT to it's right position and for this it swaps ...

so see in ascending array  1234567 , choose pivot 4 then guess as it's already at it's right position so it gives us guess that it won't need much swaps..

but when array is descending 7654321 to set 4 to it's right position we have to set 123 to it's right for this we need to swaps elements ...so in that way we can guess that this would need more swaps..

but like first case the complexity of swaps for both these cases won't be different.
0
Cool. Thank you for all the detailed explanation. :)