Stable Sort

[gear2d]

I was wondering if any one example can explain to me what is a stable sort? My professor said that the two orders will be persevered when sorting, what orders? He did any example with selection sort on this array:

A = {2 5 3 4 5 6 3}

After sorting everything he said that selection sort is unstable. Is the reason why its unstable is say you have c = {a,b} where "a" is the index number in above array, and "b" is the value at index "a". So say for 6 and 3 at the end c = {5, 6} and c={6,3} so when you swap these two now its c={5,3} and c={6,6}, is this reason why its not stable because the index positions and its corresponding values changed after the sort? If that is the case, how is bubblesort a stable sort then?

[Zachm]

I think that this link (http://en.wikipedia.org/wiki/Sorting_algorithm) explains the meaning of stable vs. unstable sorting algorithm's quite well.
I think that you had it a little wrong there, each c represents a tuple of key and value and NOT index and value.
Keep in mind that often each index in an array or other DS holds both key and value, where sorting is usually done according to the keys. In this case, there might be a scenario where you would like to sort the elements according to the keys, but if 2 elements A and B have the same key, and A originally(before sorting) appears before B, then one might like to preserve this order, meaning that after the sort, A will also appear before B. This is called stability.

Having this in mind, can you now tell why bubble sort is stable ?

Regards,
Zachm

[gear2d]

From what you and wiki say, bubble sort is stable because it swaps elements that are of different value. So say we have 1 3 1' 5 6 7 6' 8 then bubble will do

1 1' 3 5 6 7 6' 8
1 1' 3 5 6 6' 7 8

it preserve the 1 and 6 that came before the 1' and 6'. If you rewrite bubble to swap when two values are not < but <= then stability will lost since it will switch the position of two equal values regardless of the position it was in (if it came first or last). Would this be correct?

[Zachm]

it preserve the 1 and 6 that came before the 1' and 6'. If you rewrite bubble to swap when two values are not < but <= then stability will lost since it will switch the position of two equal values regardless of the position it was in (if it came first or last). Would this be correct?

Yes, it would be correct :thumb: !