PDA

View Full Version : SORT inconsistency



hcrisp
05-28-2009, 02:53 PM
I have been experiencing a bug and narrowed down the root cause to inconsistent results being returned from the SORT function. Why does SORT return inconsistent results for some arrays that have identical values? (I am using WAVE 8.00.)

Here is an example (note that the last two values in x are identical):



x = [ $
- 704.168, 718.279, 724.123, 742.193, 752.833, 756.059, 758.611, 795.843, $
- 800.134, 812.527, 819.983, 823.791, 840.027, 845.621, 848.833, 852.911, $
- 856.984, 876.411, 883.356, 898.462, 906.669, 910.427, 918.819, 937.139, $
- 957.278, 964.555, 965.587, 970.84, 985.79, 994.614, 1015.01, 1025.53, $
- 1039.92, 1041.08, 1050.85, 1064.61, 1073.62, 1084.09, 1094.74, 1104.14, $
- 1118.01, 1120.84, 1127.95, 1145.26, 1154.15, 1158.76, 1173.95, 1177.08, $
- 1194.32, 1202.45, 1204.1, 1222.23, 1228.94, 1244.32, 1249.55, 1261.99, $
- 1270.94, 1280.07, 1294.96, 1293.08, 1306.4, 1316.03, 1335.7, 1341.68, $
- 1349.82, 1356.07, 1374.65, 1381.12, 1387.65, 1391.99, 1407.44, 1407.45, $
- 1427.68, 1432.26, 1448.57, 1460.4, 1460.4]
info, x
; X FLOAT = Array(77)
info, sort(x)
; <Expression> LONG = Array(77)
print, (sort(x))(75:76)
; 75 76
print, (sort(x))(75:76)
; 76 75


You can see when I print the sorted IDs that sometimes the last two elements are switched -- first, last ... then last, first. Why is SORT doing this? I need it to be returning the indices consistently, even when the values are identical.

ed
05-28-2009, 04:33 PM
This is a common feature of many sorting algorithms. Since x(sort(x)) will always be the same even if the indices float around for equal elements, in most cases performance is more important than deterministic behavior.

If the order must be retained, you can use the User Library function "sort2".

hcrisp
05-29-2009, 06:54 AM
Ah, thanks! I did not know SORT2 existed. Looking at the source code for SORT2 gives more explanation of how the methods differ:



SORT2 returns the subscripts to sort an array without permutation of elements already in order. SORT may or may not permute sorted elements.
...
Stable sorting is important when the first element of a series of duplicates is to be selected or there are other attributes associated with the array. Unstable sorting does not maintain order within a sequence.