1. QuickSort(sorting)

Hi guys, I just want to clear out really I'm not trolling so if anyone thinks it's already simple and why I ask, because I still confused about.

What's confusing me is when we call function partition in function quicksort we will get an element sorted, my question why in the next iteration we are not taking into consideration that sorted element? because it sorted? but we still need to look at it to compare, no?!
why if an element sorted we discard it and just looking to other elements?!

isn't there's any algorithm while sorting still looking on the sorted element?

to sum up, I'm intending to say, must I be fully ordered logically to succeed interact with the PC? thanks

thanks!

2. Originally Posted by RyanC
why in the next iteration we are not taking into consideration that sorted element? because it sorted?
Yes.

Originally Posted by RyanC
but we still need to look at it to compare, no?!
No.

Originally Posted by RyanC
isn't there's any algorithm while sorting still looking on the sorted element?
Yes.

Originally Posted by RyanC
to sum up, I'm intending to say, must I be fully ordered logically to succeed interact with the PC?
Huh?

3. It depends on the quicksort implementation. Some variations of Hoare like partition schemes don't move the pivot to it's sorted position until near the deepest stages of the algorithm, such as this one shown on youtube. Note that the pivot element is skipped over during the first swap stage. In this example, partition only swaps to end up with elements < pivot to the left of element > pivot, leaving elements = pivot, including the pivot, unmoved.

4. Originally Posted by laserlight
Yes
lemme explain what's confusing me maybe because I'm converting it to real life analogous .. so it gets harder sometimes to understand the problem....

in real life analogues to quicksort, lets say I have lists of numbers and I want to sort them "myself sorting", so if I have one element sorted in the list on specific place, and while looking to the right side of that specific place I also look always at "the element" that already sorted in the specific place.. although I know its sorted.. but I keep "looking at it!".....so because I keep looking at it .. I visualize that it musn't be discarded while coding ..that makes me to be confused..

5. How could you know which elements are less than or greater than the already-sorted element unless you compare to it?

6. Originally Posted by RyanC
and while looking to the right side of that specific place I also look always at "the element" that already sorted in the specific place.. although I know its sorted.. but I keep "looking at it!".....so because I keep looking at it .. I visualize that it musn't be discarded while coding ..that makes me to be confused..
You're talking about after having partitioned based on the pivot and slotting the pivot into place, right? Why do you keep looking at the previous step's pivot when you should be comparing elements to the current pivot? The previous step's pivot isn't discarded, it is just no longer messed around with because you've moved on to the next recursive step. If in a "real life analogue" you keep looking at it, then that's your own problem. You're just wasting your own time. Why don't you look outside the window as well and ask why doesn't quicksort look outside of the window?

7. Originally Posted by laserlight
You're talking about after having partitioned based on the pivot and slotting the pivot into place, right? Why do you keep looking at the previous step's pivot when you should be comparing elements to the current pivot? The previous step's pivot isn't discarded, it is just no longer messed around with because you've moved on to the next recursive step. If in a "real life analogue" you keep looking at it, then that's your own problem. You're just wasting your own time. Why don't you look outside the window as well and ask why doesn't quicksort look outside of the window?
I got you ! that's because our "pivot" in every iteration call of the recursive will be in its own "exact" position, so it's just a dumbness to look at it as we always aim to "solve" the problem
and afterwards solving its the sub problems accordingly to the pattern that we solved the first call of the problem.

thanks

8. Originally Posted by RyanC
That's because our "pivot" in every iteration call of the recursive will be in its own "exact" position
I've already posted that this depends on the specific implementation of quicksort. The example I mentioned doesn't move the pivot or any elements equal to the pivot. A standard Hoare partition algorithm includes the pivot in one of the two parts after a partition step (if I recall correctly, the pivot or an element equal to the pivot will end up on either the right side of the left part or the left side of the right part). A standard Lomuto partition algorithm does exclude the pivot when making recursive calls. Links to wiki article sections (Lomuto, Hoare):

Quicksort - Wikipedia

Quicksort - Wikipedia

Hoare partition scheme could be modified to exclude the pivot, but a standard Hoare partition algorithm does not do this.