what happens to identical items in a sort? (sorting algorithm) for example what would the following list look like after it has been sorted in ascending order: (f, g, a, r, s, g, a, x)
+4
A:
It depends on the sorting algorithm you use.
Some algorithms are stable which means that equal but distinct items will stay in the same order that they started. Others are unstable which means that the order may change.
In your example, you'd definitely end up with (a, a, f, g, g, r, s, x) but you can't tell the difference between the equal elements. Suppose instead that we start with (f1, g1, a1, r1, s1, g2, a2, x1) and only sort by first letters. A stable sort would guarantee that we ended up with (a1, a2, f1, g1, g2, r1, s1, x1) - whereas an unstable sort could end up as (a2, a1, f1, g1, g2, r1, s1, x1) or something similar.
See the Wikipedia sorting entry for more information, and details about the stability of various algorithms.
Jon Skeet
2010-07-23 07:02:18
... and in this specific case it's immaterial, since the identical elements are truly identical. The difference between stable and unstable algorithms appear when different elements have the same sorting key (and are therefore identical to the sort)
Javier
2010-07-23 07:04:18
@Javier: Yes - that's what I meant by "you can't tell the difference between the equal elements".
Jon Skeet
2010-07-23 07:05:08
lol. Beat by the skeet. Darn
controlfreak123
2010-07-23 07:05:31
heh, you get to edit your post without traces eh?
Javier
2010-07-23 07:09:23
@Javier: Anyone gets to edit their own posts within the first five minutes without it showing up.
Jon Skeet
2010-07-23 07:16:09
+1
A:
Depends on the implementation and type of sort you perform. Some are Stable which means they preserve the original ordering (the first g will stay in front of the second). Some are unstable (can't guarantee first g will stay ahead of second)
controlfreak123
2010-07-23 07:05:02