_ArraySort on 2D is not stable but the documentation says it is

[anonymous]

_ArraySort claims to be stable in its in-script documentation if you look at the "modified" header.

LazyCoder - added $iSubItem option;
Tylo - implemented stable QuickSort algo;
Jos - changed logic to correctly Sort arrays with mixed Values and Strings;
Melba23 - implemented stable pivot algo

If you want to sort 2D arrays then the help file tells you that only quick- or insert-sort is used on these (a closer look on the Array.au3 shows you that only quicksort is used).

But if you sort with this code for example you will see that the array tells you that [5, Cherry] comes before [3, Cherry] where it should be the other way round since this algorithm is supposed to be stable.
Stable algorithms do not change the order of items if they equal the compared value.

If you look at the __ArrayQuickSort2D inside of the Array.au3 you will see that elements are swapped if $L is less or equal than $R. (l. 1813 commented with ; Swap on 3.3.14.2)

First the array is sorted on its first column showing that [3, Cherry] comes before [5, Cherry] and then you can see that after sorting the second column they are switched.

Code to reproduce:

#include <Array.au3>

Local $aTestArray[5][2] = [[5, "Cherry"], [4, "Banana"], [3, "Cherry"], [2, "Orange"], [1, "Apple"]]

;Sort the whole array ascending on the first column
_ArraySort($aTestArray, 0, 0, 0, 0)
_ArrayDisplay($aTestArray)

;Sort the whole array descending on the second column
_ArraySort($aTestArray, 0, 0, 0, 1)
_ArrayDisplay($aTestArray)

This also happens on the 3.3.14.5.

[Jos]

.. and what is the bug in your mind?
They are properly sorted on the indicated column and there is no given which sequence "records" with a similar key will be.

Jos

[anonymous]

The bug is that the algorithm claims to be stable which it is not.

If you sort the second column than you compare these elements with each other.
If you find two identical keys then you are not allowed to switch them in a stable algorithm.

You don't need to give an extra parameter to decide which keys to compare explicitly for stability, you could but you don't have to. And if you don't the usual way would be to take the items in the column you're sorting in.

These items are switched if the an item is lower or equal / greater or equal but changing that to lower / greater would cause the algorithm not to switch items (on equality) therefore resulting in a stable algorithm.

Either the implementation of the 2D sort has to change (1D sort with InsertionSort should be stable) or the documentation simply has to be altered because one of them is not correct.

[Jos]

In case you feel something is really wrong then simply submit a proposal to "fix" is, but I am not convinced that you correct about not being allowed to change the order of the records in case the primary key is equal.

Jos

[Melba23]

If you want to sort items where you want the columns to act as groupings then use my ArrayMultiColSort UDF - the link is in my sig.

M23

[anonymous]

Well I implemented my own stable algorithm by using MergeSort and expanding it into two dimensions (using the sorting column as the equality check) and it seems to work quite good.

The decision is up to the devs what now the solution of this ticket be.
Change the documentation to call the quicksort algorithm (1D and 2D) unstable or implement an existing stable solution (for example Melba's) or just leave everything how it is.

I would be very happy to see a _ArraySortStable or _ArraySort with a parameter flag to use a stable algorithm while sorting since this would be very useful in the standard UDF library.

Thanks for your efforts, ticket can be closed after a final answer please.

[Melba23]

Please post your code so that we can see what you did.

M23

[anonymous]

Sure thing!

I don't know how to attach files here so I have to link this from the german forum.
​https://autoit.de/wcf/index.php?attachment/85741-arraysortstable2d-au3/

The example code remains almost the same

#include <Array.au3>
#include "_ArraySortStable2D.au3"

Local $aTestArray[5][2] = [[5, "Cherry"], [4, "Banana"], [3, "Cherry"], [2, "Orange"], [1, "Apple"]]

;Sort the whole array ascending on the first column
_ArraySortStable2D($aTestArray, 0, Default, Default, False) ; Col = 0, Start = Begin, End = End, Ascending
_ArrayDisplay($aTestArray)

;Sort the whole array descending on the second column
_ArraySortStable2D($aTestArray, 1, Default, Default, False) ; Col = 1, Start = Begin, End = End, Ascending
_ArrayDisplay($aTestArray)

The result is correct and I tried this in my current project where I sort items with the ListView (which sorts them using a stable algorithm).
I tested around 500 items on various colums and always got the same result.

If there is one thing that might not match, it will be the compare function.

[anonymous]

This was fairly a quick UDF so I might be changing a few things in the next few days.
The compare function uses StringUpper and does not recognize Uppercase and Lowercase differences.

But that is just a rather small issue and nothing serious.

[Melba23]

Removed "stable" words from function header - function code unchanged

Changed by revision [12302] in version: 3.3.15.3