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[1]=6 which is <=PIVOT(7) => Now L=0+1=1 and swap a[1] to a[1] // 1 swap
a[2]=5 which is <= PIVOT(7) => Now L=1+1=2 and swap a[2] to a[2] // 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