ME-Quick Sort

Question

Comments

@srestha are talking abt 1st pass??

---

yes , we have just choosen 15 as pivot.

So, after applying quick sort, while 15 as pivot, we get elements are

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

So, only 12 is in previous position

All other changes their position

---

i think 6  is the answer if we use standard partition allgorithm....

Answer 1

If I swap 15 with the last element, then 12 and 16 remain unchanged !!

Then, total elements which change their positions are 6.

---

If I swap 15 with the first element, then only 16 remains unchanged !!

Hence, in this case the elements which change their positions are 7.

---

This question is ambiguous as i think it should give the position. But if not given( like here ), i would go with the maximum .i.e, 7.

As in both the case only 16 is constant by any method, we apply and all others (CAN) change their position means they are having the ability to change their positions . Hence I suppose , 7 should be correct .

Comments

How 11 is getting swapped..could please post the image?

---

https://gateoverflow.in/36401/quick-sort

https://gateoverflow.in/19278/partitioning

https://gateoverflow.in/27904/sorting

Answer 2

7 ans

Comments

if I swap 15(pivot) with the last element of the array(14), I am getting answer 6.

---

Why can't we keep 15 at last position and then apply partitioning algorithm? That way, answer will be different.

---

even i m doing ame thing

1st i have swapped 15 with last element then applied partition hence getting 6 as answer

Answer 3

Answer will be (7).

Comments

change the position of pivot , if needed more clarification see the below comment.

---

Below partitioning is fine when we take pivot as first element.. But if we take pivot as last element,Both 12,16 remain at their position

---

Even I am getting 6. I refered QUick sort algorithm video by mycodeschool.com - youtube.

Answer 4

simply make one move in the beginning to swap the 15 to position from where u are comfortable to apply quick sort algorithm either at middle, first position or last.

Comments

yes u have that value in a temporary variable but then after the partition loop the final step is to swap pivot element and (the position where smaller value pointer is + 1). but since you swapped it u either would have to take another variable to remember its position or do not move it at all.

---

@Aspi You are right. I do not think "quicksort" enforces a "pivot" algorithm. It is up to implementation to do this. So, there is no fixed answer here- only the best case can be there.

---

Please tell me where i am wrong

Answer 5

You have to choose 15 here as pivot element.

The sequence becomes after first pass will be

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

Comments

okay check that and correct me ...

---

I think you are correct.

Because elements 12,11,16 will not change their position. Are you also getting the same ?

---

Yes i am getting same only... thtz why i have doubt.. how to consider answer here?

Answer 6

Before partition Algo	12	18	17	11	13	15	16	14
After partition Algo	14	11	13	12	15	18	16	17

7 elements change their position

Comments

how you getting 7 i am getting 6 after following algo given in clrs. 

first i swap last elemnet and 15 ie 14 and 15 then applied partition

initial  12	18	17	11	13	15	16            14
final     12	11	13	14	15	18	16             17

---

i swapped with first element