Thread: QuickSort(sorting)

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    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!
    Last edited by RyanC; 12-27-2018 at 01:36 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by RyanC
    why in the next iteration we are not taking into consideration that sorted element? because it sorted?
    Yes.

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

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

    Quote 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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    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.

    YouTube
    Last edited by rcgldr; 12-27-2018 at 02:27 PM.

  4. #4
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    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. #5
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    How could you know which elements are less than or greater than the already-sorted element unless you compare to it?
    Last edited by bruteforce; 12-27-2018 at 06:41 PM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    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. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by RyanC View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 24
    Last Post: 09-05-2016, 12:23 PM
  2. quicksort
    By WelshGrandSlam in forum C++ Programming
    Replies: 8
    Last Post: 01-23-2008, 08:15 PM
  3. Quicksort
    By lerqa in forum C Programming
    Replies: 3
    Last Post: 01-15-2008, 05:32 PM
  4. help with quicksort
    By Darkinyuasha1 in forum C Programming
    Replies: 4
    Last Post: 12-04-2007, 05:32 PM
  5. Quicksort
    By OnionKnight in forum C++ Programming
    Replies: 3
    Last Post: 05-28-2005, 06:55 PM

Tags for this Thread