So the question is to construct a best case example for Quick Sort with 15 elements n = 15, hopefully somebody could give me a second opinion to whether this is the best case for this Quick Sort implementation.
The way the algo works for this exercise is that pivot will always be the last element.
Now as you will see in the picture we have a (j). (j) will be at first position initially. If value at that position is smaller than pivot, it will move to next element.(what actually happen is that it switches with the element itself but since the element is at same position nothing happened). Now if let say the value at (j) is larger than pivot then (j) stays where it is waiting for next element that is smaller than pivot then (j) and that element will switch.
Lastly, the pivot will switch position with the j element.
You may wonder why we still consider for when p(begining element) == q (last element) but that is just the way this exercise is Ex:(G(1,1), G(3,3),...) in these case we still call the function but will do nothing.
Hint teacher gave was: best case has to do with the least number of exchanges in a partition when comparing with the pivot M.
My thinking was to construct it bottom up and make sure both side of the tree will always equal hence prevent situtation when the pivot wont go into the middle but stay at side (aka list is almost sorted and we have a tree that is skewed to one side)
Thank you for helping out!
