Modify

Opened 19 months ago

Last modified 19 months ago

#3620 new Bug

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

Reported by: anonymous Owned by:
Milestone: 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 (8)

comment:1 Changed 19 months ago by 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

comment:2 Changed 19 months 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 19 months 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

Last edited 19 months ago by Jos (previous) (diff)

comment:4 Changed 19 months 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 19 months 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 19 months ago by Melba23

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

M23

comment:7 Changed 19 months 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 19 months 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.

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.

Add Comment

Modify Ticket

Action
as new The ticket will remain with no owner.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.