#3620 closed Bug (Completed)
_ArraySort on 2D is not stable but the documentation says it is
Reported by: | anonymous | Owned by: | Melba23 |
---|---|---|---|
Milestone: | 3.3.15.3 | Component: | Documentation |
Version: | 3.3.14.2 | Severity: | None |
Keywords: | _ArraySort Stablity | Cc: |
Description
_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.
Attachments (0)
Change History (10)
comment:1 Changed 6 years ago by Jos
comment:2 Changed 6 years ago by 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.
comment:3 Changed 6 years ago by Jos
In case you feel something is really wrong then simply submit a proposal to "fix" this UDF, 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
comment:4 Changed 6 years ago by 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
comment:5 Changed 6 years ago by 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.
comment:6 Changed 6 years ago by Melba23
Please post your code so that we can see what you did.
M23
comment:7 Changed 6 years ago by 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.
comment:8 Changed 6 years ago by 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.
comment:9 Changed 4 years ago by Jpm
- Owner set to Melba23
- Status changed from new to assigned
comment:10 Changed 4 years ago by Melba23
- Milestone set to 3.3.15.3
- Resolution set to Completed
- Status changed from assigned to closed
Removed "stable" words from function header - function code unchanged
Changed by revision [12302] in version: 3.3.15.3
Guidelines for posting comments:
- You cannot re-open a ticket but you may still leave a comment if you have additional information to add.
- In-depth discussions should take place on the forum.
For more information see the full version of the ticket guidelines here.
.. 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