partitioning

Question

Consider the following array...

12 18 17 11 13 15 16 14

Find the no of elements which will change  their position when partitioning algorithm is applied on array .pivot choosen is 15

Comments

Even I am getting 6.

Elements after partitioning I got are:

12 11 13 14 15 18 16 17

---

it has to be 6..itself !

---

I applied Quicksort directly.

Answer 1

We can choose any random element as pivot

Here 3rd last element 15 as pivot 

 So, as 17, 18 greater than pivot ,17, 18 will go after 15

and 14 less than pivot, so,14 will come before 15

12,11,13,14,15,18,17,16......................here 3 element change its position

Now 13 pivot, No change in element

Now 12 as pivot 11 will change its position...........here 1 element change position

11,12,13,14,15,17,16,18

Now 18 as pivot 2 element change its position

12,11,13,14,15,17,16,18........................here 2 element change position

Now 17 as pivot 16 will change its position..............here 1 element change its position

Here  total no of element change its position is 7

Comments

Answer given for this question is 7 but I m getting 6. Plezz explain how it can be 7.

---

ok

---

but in this question it is asking the number of elements changed their position when the pivot is 15 .

---

only 15 as pivot then 3 will be ans

Answer 2

12, 18, 17, 11, 13, 15, 16, 14.   15 is pivot swap it with right most element

12, 18, 17, 11, 13, 14, 16, | 15

12, 11, 17, 18, 13, 14, 16, | 15

12, 11, 13, 18, 17, 14, 16, | 15

12, 11, 13, 14, 17, 18, 16, | 15

12, 11, 13, 14, 15, 18, 16, | 17

12, 11, 13, 14, 15, 18, 16, 17

clearly 12 and 16 are not changed.

if we use pivot as leftmost element then 16 doesn't change

12, 18, 17, 11, 13, 15, 16, 14.   15 is pivot swap it with left most element

15 | 18, 17, 11, 13, 12, 16, 14

15 | 11, 17, 18, 13, 12, 16, 14

15 | 11, 13, 18, 17, 12, 16, 14

15 | 11, 13, 12, 17, 18, 16, 14

15 | 11, 13, 12, 14, 18, 16, 17

14 | 11, 13, 12, 15, 18, 16, 17

in this case answer is seven

Comments

it is the case of central  element . I think so

Answer 3

METHOD 1 : Pivot Choosing as Middle Element

step1: Elements greater than 15 move  to right hand side of 15  in same order.

step2: Elements which are less than 15 put in same order when they are LHS of 15 else move them to ahead of 15 in same order.

step3: Fix the position of 15.

After doing this arrangements of array elements are:  

12 11 13 14 15 18 17 16 

Ans=7

METHOD 2 : Pivot Position is choosen as Right Most Element

12, 18, 17, 11, 13, 15, 16, 14.   15 is pivot swap it with right most element
12, 18, 17, 11, 13, 14, 16, | 15
12, 11, 17, 18, 13, 14, 16, | 15
12, 11, 13, 18, 17, 14, 16, | 15
12, 11, 13, 14, 17, 18, 16, | 15
12, 11, 13, 14, 15, 18, 16, | 17
12, 11, 13, 14, 15, 18, 16, 17
clearly 12 and 16 are not changed.

Ans= 6
 

METHOD 3 : Pivot Position is choosen as Left Most Element

if we use pivot as leftmost element then 16 doesn't change

12, 18, 17, 11, 13, 15, 16, 14.   15 is pivot swap it with left most element
15 | 18, 17, 11, 13, 12, 16, 14
15 | 11, 17, 18, 13, 12, 16, 14
15 | 11, 13, 18, 17, 12, 16, 14
15 | 11, 13, 12, 17, 18, 16, 14
15 | 11, 13, 12, 14, 18, 16, 17
14 | 11, 13, 12, 15, 18, 16, 17

Ans = 7

Clearly this is Ambiguous Question . We need to know the position of Pivot Element   .  Made Easy has asked the same in Last Year Test Series as well

• GATE 2016 Made Easy  Test Series

Comments

@santhosh
This Question is ambiguous !
They should mention position of Position of Pivot also. Here we will get two different answers . Hopefully  GATE questions will not be this much ambiguous

---

can u help me with the 1st method ? its algo ?

---

This is question  very good 

passes are like this

12 11 17 18 13 15 16 14 >>> 11 and 18 changes it's initial position

12 11 13 18 17 15 16 14 >>>13 and 17 changes it's initial position

12 11 13 14 17 15 16 18 >>>here 14 and 18 will swap but only 14 will change initial position

12 11 13 14 15 17 16 18>>>>here 15 and17 will swap but 15 will change initial position

according to me answer is 6

Answer 4

12 18 17 11 13 15 16 14
First swap the pivot element to first place of array so 15 18 17 11 13 12 16 14

Now after the partition algo     ( i followed this algo)
partition(a,p(first element),q(last element))

{
x=a[p];
i=p;
for(j=p+1;j<=q;j++)

{
         if(x>=a[j])
                 {                      
                       i=i+1;
                     swap(a[i],a[j]);
                  }
             swap(a[i] ,a[p]);
            return 0 ;
}

e.g  
                                  x
                                  i  j
                                 15 18 17 11 13 12 16 14  condition fails
                                         j
                                  15 18 17 11 13 12 16 14  condition fails
                                      i     j
                                  15 18 17 11 13 12 16 14  condition true i will be incremented swap a[i],a[j]
                                  15 11 17 18 13 12 16 14 after swap again loop will check
                                         i    j  
                                  15 11 17 18 13 12 16 14 condition true i will be incremented swap a[i],a[j]
                                  15 11 13 18 17 12 16 14 after swap again loop will check
                                            i     j
                                  15 11 13 12 17 18 16 14 condition true i will be incremented swap a[i],a[j]
                                  15 11 13 12 17 18 16 14 after swap again loop will check
                                            i        j
                                  15 11 13 12 17 18 16 14  condition fails
                                               i        j
                                  15 11 13 12 17 18 16 14 condition true i will be incremented swap a[i],a[j]
                                  15 11 13 12 14 18 16 17 here j>q so loop ends
                 
       now swap a[i] a[p]         14 11 13 12 15 18 16 17  

    14 11 13 12 15 18 16 17
So 7 element changed their position after the partition algo.

Comments

Can u explain each step....and which version of partitioning u applied???

---

i is at first position in starting whenever smaller number is found i is incremented and swapped with j!

---

Why swap 15 at first index?? why not end?? why not direct start applying partition method.

Answer 5

I think 7 is correct.Check?

#include<stdio.h>
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
int main()
{
    int arr[]={15,18,17,11,13,12,16,14};
    int   p=0;
	int x = arr[p];
	int i = p ,j;
    for ( j =p+1; j<=7; j++)
	{
		if (arr[j] <= x)
		{
			i++;
			swap (&arr[i], &arr[j]);
		}
	}
      swap (&arr[p], &arr[i]);

	int k;
    for (k=0; k<=7; k++)
        printf("%d ", arr[k]);
        printf("\n");
}

Note:Above code picking first element as pivot.