recategorized by
946 views
4 votes
4 votes

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 ?

recategorized by

1 Answer

Best answer
0 votes
0 votes

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

selected by

Related questions

2 votes
2 votes
3 answers
3
LavTheRawkstar asked Apr 15, 2017
1,186 views
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9).Analysis the time complexity of Quick sort in the best case.
1 votes
1 votes
1 answer
4
Saurabh Sharma asked Jul 22, 2015
1,049 views
THISCOURSEISOVERChoose the last elements as pivot elements (R). Also for duplicates, adopt the convention that both pointers stop.a) EHIOCOIERRUSSVTSb) EHISCOIERRUSOVTSb)...