-
November 24th, 2005, 05:49 PM
#1
What does it mean that a sorting algorithm is stable?
Any one can give me an idea? Thanks for your inputs.
-
November 24th, 2005, 06:14 PM
#2
Re: What does it mean that a sorting algorithm is stable?
It means that items that already are sorted keeps their relative position.
Ex. if you got this list:
When sorted it becomes this:
This result is 'stable' because the two '2' are in the same order as they were before sorted (the red one before the green one).
An unstable result might look like this (Here the green one comes before the red one):
- petter
-
November 24th, 2005, 11:50 PM
#3
Re: What does it mean that a sorting algorithm is stable?
WildFrog,
As per your statement "This result is 'stable' because the two '2' are in the same order as they were before sorted (the red one before the green one)."
How we are sure that it was sorted earlier? (Assumption: The initial list is a raw list) What if the list is 212 ?
I believe there will be one more key/element to differentiate between Green and Red 2.
-PiyuNewe
-
November 29th, 2005, 06:06 PM
#4
Re: What does it mean that a sorting algorithm is stable?
For what I know, a <em>stable</em> algorithm must not swap the relative positions of "similar" (equivalent) elements with respect to their positions in the original input.
This means, for example, that a list such as:
2 (first "2), 1 (first "1"), 3 (first "3"), 2 (second "2")
shall be sorted as:
1 (first "1"), 2 (first "2"), 2 (second "2"), 3 (first "3)
It is not that the numbers were "sorted" earlier... it is just a thing about where they were in the list.
As a better example, supose that you are sorting cars, by their brand names. Then, each car also can have its own color. A stable sorting guarantees that, if you were sorting by brand names, not only the sorting works, but if you had a "green Hyundai" and then a "blue Hyundai" and then a "red Hyundai", in that order, anywhere in the list, then the resulting sorted list is guaranteed to have the Hyundais in the sequence: some Hyundai, ... , green Hyundai, blue Hyundai, red Hyundai, ... , other Hyundai.
Hope it helps.
You're not watching "24"?
Well... you should.
24
Jack IS back...
-
November 29th, 2005, 07:19 PM
#5
Re: What does it mean that a sorting algorithm is stable?
Thanks for clearing that up, Luchin_plusplus.
I wrote a followup to my first post to trying to somewhat ******** my points, but it seems that I forgot to click 'submit'.
Anyway, working with arrays (like a simple list of numbers) there is no practical difference if the sorting algorithm is stable or not. But, when you add a second dimension (like car colors) you''ll see a difference.
- petter
-
November 30th, 2005, 05:30 AM
#6
Re: What does it mean that a sorting algorithm is stable?
Thanks Luchin_plusplus and Wildfrog.
-PiyuNewe
-
December 1st, 2005, 02:15 PM
#7
Re: What does it mean that a sorting algorithm is stable?
Originally Posted by PiyuNewe
Thanks Luchin_plusplus and Wildfrog.
Originally Posted by wildfrog
Thanks for clearing that up, Luchin_plusplus.
You're welcome!
Stablesorting is important to gather and preserve real-world information. Cars are not just cars, they may be Hyundai red cars, or Nissan blue cars. When you need to sort information and preserve some internal properties of the original list, then you go for stablesorting (such as in a database).
Continuing the topic, I am not very familiar with this, but is there a way to determine if a sorting algorithm is stable? or is it something that "you're born with"?
You're not watching "24"?
Well... you should.
24
Jack IS back...
-
December 3rd, 2005, 07:26 AM
#8
Re: What does it mean that a sorting algorithm is stable?
but is there a way to determine if a sorting algorithm is stable? or is it something that "you're born with"?
The 'easy' way is to just examine the output is stable or not. One problem with this approach is that it might return 1000 stable results, and then suddenly the 1001. result is unstable.
The best approach is to dig deep and examine how the algorithm actually works.
- petter
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|