std::stable_sort()

This is a discussion on std::stable_sort() within the C++ Programming forums, part of the General Programming Boards category; I've been re-reading Scott Meyer's chapter about STL sorting algorithms, and I was wondering when someone would want to use ...

  1. #1
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545

    std::stable_sort()

    I've been re-reading Scott Meyer's chapter about STL sorting algorithms, and I was wondering when someone would want to use stable_sort() instead of just sort()?
    If two objects are equivalent, what difference does it make which one precedes the other? They are equivalent after all...
    So far, the only case I could think of for using stable_sort() is if you need to sort a container twice -- once for one criteria, then again for another criteria and you don't want to lose the sorting done in the first sort.

    Can anyone tell me what other situations you would use a stable_sort() for and how often people actually use it in their code when they need to sort something?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,582
    So far, the only case I could think of for using stable_sort() is if you need to sort a container twice -- once for one criteria, then again for another criteria and you don't want to lose the sorting done in the first sort.
    I believe that is general idea, since stable_sort only makes sense when objects have more than one property. Of course, the container (or rather, range) may not even be sorted by the program to begin with.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Consider that you have a "compare" operator that doesn't compare ALL parts of the object - say you have a
    Code:
    class person
    {
        string name;
        string street;
        string city;    
    public:
        ....
        bool operator>(person &p) {
            return p->name > name;
        };
    };
    Now, you may not want to swap the "Steve Jones" that live on "London Road" and the "Steve Jones" that live on "Newport Road"?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Imagine a grid or table that is sorted based on whichever column the user clicks. If the user wants to sort by name and then date, first they click on the date column and the data is sorted by that property, then they click on the name column and stable_sort is used to make sure that all the rows with the same name are sorted by date.

    I often wish the Windows Explorer had this feature.

  5. #5
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by Daved View Post
    Imagine a grid or table that is sorted based on whichever column the user clicks. If the user wants to sort by name and then date, first they click on the date column and the data is sorted by that property, then they click on the name column and stable_sort is used to make sure that all the rows with the same name are sorted by date.

    I often wish the Windows Explorer had this feature.
    OK, that's basically the use-case I came up with.
    I don't write GUI's since I have absolutely no artistic style, but I suppose column sorting is one place stable_sort() would (or should) be used a lot.
    But are there any cases you'd use it other than sorting based on multiple criteria (i.e. sorting using a single call to stable_sort())?

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    The only reason I think you would use it is if you had an existing sort applied to the data that you wanted to keep for elements that are equivalent in the new sort. That would only happen if there are more than one sorting criteria.

    Technically, you can be using more than one sorting criteria but still only call stable_sort once. For example, if you insert data in a particular order and want to sort it but leave equivalent values in the order they were inserted then you would call stable_sort just the one time.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    An early version of UT2004 used to use a non-stable sort for sorting the list of servers by ping time every now and then, as more were pinged. The problem was that there might be 3 say that all have a 50ms ping time exactly, and those 3 would constantly change order whilst others were being added to the list and the list resorted. This made it hard to click on the right one. Quite likely this was fixed by using stable_sort. Though they may have simply added disambiguation criteria to the comparison function.

    That's the best real-world example I have. Actually it's the example I have on my website.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by iMalc View Post
    An early version of UT2004 used to use a non-stable sort for sorting the list of servers by ping time every now and then, as more were pinged. The problem was that there might be 3 say that all have a 50ms ping time exactly, and those 3 would constantly change order whilst others were being added to the list and the list resorted. This made it hard to click on the right one. Quite likely this was fixed by using stable_sort. Though they may have simply added disambiguation criteria to the comparison function.

    That's the best real-world example I have. Actually it's the example I have on my website.
    Aha! I knew there had to be some other reason other than double-sorting. Thanks.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    imalc, if I understand you correctly that might be solved by using insertion sort? (Which appears to be a stable sort, though.)

    I am actually using insertion sort for high-scores in a game. The stableness is important, except that most recently added equivalent scores would get the highest place.
    Last edited by anon; 01-10-2008 at 11:36 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Off-topic, but in a high score list the most recently added equivalent score should get the lowest place.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You are probably right.

    However, I recorded only the 10 best results, and I figured that once the highscores get reasonably high, you'd at least get the satisfaction of entering your name (which defaults to currently logged on username to save some trouble) and being congratulated on making it to Top 10 if you are able to repeat the 10th score. Especially once I went through the trouble of highlighting the most recently added line.

    I mean, you got to give people motivation to play your game

    -------------
    But anyway, my point is that highscore tables are another practical example where stable sort is needed.
    Last edited by anon; 01-10-2008 at 12:32 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by anon View Post
    imalc, if I understand you correctly that might be solved by using insertion sort? (Which appears to be a stable sort, though.)

    I am actually using insertion sort for high-scores in a game. The stableness is important, except that most recently added equivalent scores would get the highest place.
    Insertion Sort is stable, so long as you are careful about your use of comparisons (e.g. < vs <=) and get the arguments the right way around.
    You can check against the implementation on my website if you want. Link in sig.

    Your highscore example is definitely another example of where a stable sort (or part of one) should be used. You can add the new highscore at the end, perform an insertion sort (or just the last pass), and then drop off the last item.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21