Quick Algorithm Question

This is a discussion on Quick Algorithm Question within the C++ Programming forums, part of the General Programming Boards category; What is the difference between a sorting algorithm that is considered to be stable versus one that is unstable? I ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    46

    Quick Algorithm Question

    What is the difference between a sorting algorithm that is considered to be stable versus one that is unstable?

    I know that stable and unstable refer to the action that is taken when two values compare as equal. I wanted a more watered down version though so I can understand this better.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Stable sort will leave equal elements in their original relative order.
    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).

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    The stable sort leaves unchanged the relative order of elements which are equivalent (not necessarily equal) under the sort relation. The standard STL sort algorithms require a strict weak ordering as a sort relation, which allows nonequal elements to be equivalent. For example, the relation R such that x R y iff |x| < |y| is a strict weak ordering, but 5 and -5 are equivalent under it.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Imagine you had some set of records which you are trying to sort based on a specific key element -- say, Age. You already have a set of these records in some specific order, and you want to STABLY sort them based on Age. For instance, say you had this:

    Code:
    Maria, 25
    Dan, 29
    April, 29
    Bob, 19
    Tim, 25
    After a stable sort on Age, these items are in the following order:

    Code:
    Bob, 19
    Maria, 25
    Tim, 25
    Dan, 29
    April, 29
    This is "stable" because Maria still comes before Tim, Dan still comes before April. An unstable sort might have produced:

    Code:
    Bob, 19
    Tim, 25
    Maria, 25
    April, 29
    Dan, 29
    It's still sorted, but Tim now comes before Maria and April comes before Dan. This is "unstable."
    Last edited by brewbuck; 11-01-2007 at 10:41 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. quick question (C/C++)
    By owi_just in forum C Programming
    Replies: 2
    Last Post: 03-19-2005, 08:44 AM
  2. quick question
    By Unregistered in forum C++ Programming
    Replies: 5
    Last Post: 07-22-2002, 04:44 AM
  3. Quick Question Regarding Pointers
    By charash in forum C++ Programming
    Replies: 4
    Last Post: 05-04-2002, 11:04 AM
  4. Quick Question on File Names and Directories
    By Kyoto Oshiro in forum C++ Programming
    Replies: 4
    Last Post: 03-29-2002, 01:54 AM
  5. Quick question: exit();
    By Cheeze-It in forum C Programming
    Replies: 6
    Last Post: 08-15-2001, 05:46 PM

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