How to sort a 2D array on several columns using _ArraySort()

[c.haslam]

I want to sort on columns 0 to 3.

The time-honored way of doing this is to sort on the most minor column, then on the more major columns (here  3,2,1, then 0):

#include <Array.au3>

Local $ar[200][5]
For $i = 0 to 199
    for $j = 0 to 4
        $ar[$i][$j] = Chr(Random(97,122,1))&Chr(Random(97,122,1))&Chr(Random(97,122,1))
    Next
Next

_ArrayDisplay($ar, "$ar BEFORE _ArraySort()")
For $i = 3 to 0 step -1
    if not _ArraySort($ar,0,0,0,$i) Then
        MsgBox('','error',@error)
    EndIf
    _ArrayDisplay($ar, "$ar AFTER _ArraySort() ascending column "&$i)
Next

(Here, I don't care about column 4.)

But, as you can see, this progressive sort method doesn't work with _ArraySort(): it seems to sort only the values in the subject column, not to move the whole row based on values in the sort column.

Thoughts?

Edited June 14, 2015 by c.haslam

[water]

IIRC there are functions available on the forum so sort an array on multiple columns.

[Melba23]

c.haslam,

This thread is my contribution to the oeuvre.

M23

[water]

Ah, I knew it was a function you had written . Unfortunately I couldn't find it in your signature and the search funcion of the new forum is .....

[Melba23]

water,

the search funcion of the new forum is .....

It took me a couple of tries - and I knew the name of the function!

M23 

[water]

I hope the forum will soon get a better search function. Now it is horrible - to say the least

[Melba23]

water,

My wish is a simpler subset of yours: "I hope the forum will soon get [...] better [...]"

M23

[jchd]

I want to sort on columns 0 to 3.

The time-honored way of doing this is to sort on the most minor column, then on the more major columns (here  3,2,1, then 0)

No,  the normal way is to sort on the major criterion (here column 0), on equality sort on column 1, on equality sort on column 2 and on equality on column 3.

Doing things in the opposite order requires a stable sort and is three times slower the way you think of it. The basic on-place qsort implemented in many UDFs is not stable.

[c.haslam]

Thank you all.

jchd: Please tell me more about "equality sort" and "stable sort".

[jchd]

I meant: "on equality of key level N, sort on key level N+1"
It is the way you collate strings like names: first collate on the first character and on equality, collate on the second one, etc.
Strings representing integral numbers require you sort on length first, then on the string content.

A stable sort doesn't change the order of equal keys in the input.

[c.haslam]

Thank you

[Gianni]

to simplify a bit your life, you could use sql against your 2d array so to get your wanted result using an SQL query and leave the SQLite engine will work for you.
You need to download the ArraySQL udf from this post ( https://www.autoitscript.com/forum/topic/166536-manage-arrays-by-means-of-sql/?do=findComment&comment=1234441 ), and then use something like this for example:

#include <Array.au3>
#include <ArraySQL.au3> ; <-- download this from following post:
; https://www.autoitscript.com/forum/topic/166536-manage-arrays-by-means-of-sql/?do=findComment&comment=1234441

Local $ar[200][5]
For $i = 0 To 199
    For $j = 0 To 4
        ; Short random data to only one char so to better see the logic of the result.
        $ar[$i][$j] = Chr(Random(97, 122, 1)) ; &Chr(Random(97,122,1))&Chr(Random(97,122,1))
    Next
Next

_ArrayDisplay($ar, "$ar BEFORE _ArraySort()")
#cs
    For $i = 3 to 0 step -1
    if not _ArraySort($ar,0,0,0,$i) Then
    MsgBox('','error',@error)
    EndIf
    _ArrayDisplay($ar, "$ar AFTER _ArraySort() ascending column "&$i)
    Next
#ce

; returns all rows ordered first by column3 then by Column2, column1 and Column0)
$sQuery = "SELECT * FROM array ORDER BY column3,column2,column1,column0;"
$aResult = _ArraySQL($ar, $sQuery)
If Not @error Then
    _ArrayDisplay($aResult, "Ordered by column3,column2,column1,column0")
Else
    MsgBox(0, "error", $g__sSQLiteError)
EndIf

 

Edited June 15, 2015 by Chimp

[c.haslam]

Thanks, Chimp. I was wondering how to use SQLite to do the job.

[jchd]

As an aside and while I'm a very very big big big fan of SQLite I'd say that going this way should be kept for cases where the volume of data is significant, or when the sorting condition(s) is/are non trivial (or diverse: col7 ASC then (col3 & col14) DESC then upper(col5) ASC), or when there is a need to finally store the data on disk. For the last point, using the SQLite backup UDF is recommended (search will help, when/if it works).

[LarsJ]

Another way to sort a 2D array by multiple columns is binary sorting based on an index. That is, the row numbers are inserted in the index at positions corresponding to the sorting order. The array itself is not affected by the sorting.

expandcollapse popup

Func SortArray( ByRef $aItems, $pIndex, $tIndex, $aCmps )
  Local $iCmps = UBound( $aCmps ), $c, $r, $v[$iCmps]
  Local $lo, $hi, $mi
  For $i = 0 To UBound( $aItems ) - 1
    For $j = 0 To $iCmps - 1
      $v[$j] = $aItems[$i][$aCmps[$j][0]] ; Values
    Next
    $lo = 0
    $hi = $i - 1
    While $lo <= $hi ; Binary search
      $r = 0 ; Compare result (-1,0,1)
      $j = 0 ; Index in $aCmps array
      $mi = Int( ( $lo + $hi ) / 2 )
      While Not $r And $j < $iCmps                    ; This While-loop handles sorting by multiple
        $c = $aCmps[$j][0]   ; Column                 ; columns. Column values of the two rows are
        Switch $aCmps[$j][1] ; Number/string          ; compared until a difference is found.
          Case 0 ; Compare column values as numbers. The following line is an implementation of the spaceship or three-way comparison operator for numbers like StringCompare is for strings.
            $r = ( $v[$j] < $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ? -1 : $v[$j] = $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ? 0 : 1 ) * $aCmps[$j][2] ; * $iCmpAsc
          Case 1 ; Compare column values as strings. StringCompare is a spaceship or three-way comparison operator for strings.
            $r = StringCompare( $v[$j], $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ) * $aCmps[$j][2] ; * $iCmpAsc
        EndSwitch
        $j += 1
      WEnd
      Switch $r
        Case -1
          $hi = $mi - 1
        Case  1
          $lo = $mi + 1
        Case  0 ; Equal
          ExitLoop
      EndSwitch
    WEnd
    If $i > $mi Then _ ; Make space for the row number in index
      DllCall( $hKernel32Dll, "none", "RtlMoveMemory", "struct*", $pIndex+($mi+1)*4, "struct*", $pIndex+$mi*4, "ulong_ptr", ($i-$mi)*4 )
    DllStructSetData( $tIndex, 1, $i, $mi+1+($lo=$mi+1) ) ; Insert row number $i at position $mi+1+($lo=$mi+1) in index
  Next
EndFunc

Example:

expandcollapse popup

#include <Array.au3>

Opt( "MustDeclareVars", 1 )

Global Const $hKernel32Dll = DllOpen( "kernel32.dll" )

Example( 1000, 3 )


Func Example( $iRows, $iCols )
  Local $aItems[$iRows][$iCols]

  ; Fill array
  FillArray( $aItems )
  _ArrayDisplay( $aItems, "Unsorted" )

  ; Sort array
  Local $tIndex = DllStructCreate( "uint[" & $iRows & "]" )
  Local $pIndex = DllStructGetPtr( $tIndex )
  Local $aCmps[3][3] = [ _
    [ 0, 1, +1 ], _ ; Col 0: Compared as strings, asc
    [ 1, 0, +1 ], _ ; Col 1: Compared as numbers, asc
    [ 2, 0, +1 ] ]  ; Col 2: Compared as numbers, asc
  SortArray( $aItems, $pIndex, $tIndex, $aCmps )

  ; Display rows
  Local $iRows2 = $iRows, $j
  Local $aItems2[$iRows2][$iCols]
  For $i = 0 To $iRows2 - 1
    $j = DllStructGetData($tIndex,1,$i+1)
    For $k = 0 To $iCols - 1
      $aItems2[$i][$k] = $aItems[$j][$k]
    Next
  Next
  _ArrayDisplay( $aItems2, "Sorted" )
EndFunc

DllClose( $hKernel32Dll )

Func FillArray( ByRef $aItems )
  Local $aLetters[26] = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', _
                          'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' ]
  Local $s, $t, $iRows = UBound( $aItems )
  For $i = 0 To $iRows - 1
    $s = $aLetters[Random(0,25,1)]
    For $j = 1 To 9
      $s &= $aLetters[Random(0,25,1)]
    Next
    $aItems[$i][0] = $s                                                ; String
    $aItems[$i][1] = Random( 0, $iRows - 1, 1 )                        ; Integer
    $aItems[$i][2] = Random( 0, $iRows - 1, 1 ) + Round( Random(), 4 ) ; Float
    ; Duplicate strings
    For $j = 1 To Random(0,2,1)
      If $i = $iRows - 1 Then ExitLoop
      $i += 1
      $aItems[$i][0] = $s                                                ; String
      $aItems[$i][1] = Random( 0, $iRows - 1, 1 )                        ; Integer
      $aItems[$i][2] = Random( 0, $iRows - 1, 1 ) + Round( Random(), 4 ) ; Float
      $t = $aItems[$i][1]
      ; Duplicate strings and integers
      For $m = 1 To Random(0,2,1)
        If $i = $iRows - 1 Then ExitLoop
        $i += 1
        $aItems[$i][0] = $s                                                ; String
        $aItems[$i][1] = $t                                                ; Integer
        $aItems[$i][2] = Random( 0, $iRows - 1, 1 ) + Round( Random(), 4 ) ; Float
      Next
    Next
  Next
EndFunc

Func SortArray( ByRef $aItems, $pIndex, $tIndex, $aCmps )
  Local $iCmps = UBound( $aCmps ), $c, $r, $v[$iCmps]
  Local $lo, $hi, $mi
  For $i = 0 To UBound( $aItems ) - 1
    For $j = 0 To $iCmps - 1
      $v[$j] = $aItems[$i][$aCmps[$j][0]] ; Values
    Next
    $lo = 0
    $hi = $i - 1
    While $lo <= $hi ; Binary search
      $r = 0 ; Compare result (-1,0,1)
      $j = 0 ; Index in $aCmps array
      $mi = Int( ( $lo + $hi ) / 2 )
      While Not $r And $j < $iCmps                    ; This While-loop handles sorting by multiple
        $c = $aCmps[$j][0]   ; Column                 ; columns. Column values of the two rows are
        Switch $aCmps[$j][1] ; Number/string          ; compared until a difference is found.
          Case 0 ; Compare column values as numbers. The following line is an implementation of the spaceship or three-way comparison operator for numbers like StringCompare is for strings.
            $r = ( $v[$j] < $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ? -1 : $v[$j] = $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ? 0 : 1 ) * $aCmps[$j][2] ; * $iCmpAsc
          Case 1 ; Compare column values as strings. StringCompare is a spaceship or three-way comparison operator for strings.
            $r = StringCompare( $v[$j], $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ) * $aCmps[$j][2] ; * $iCmpAsc
        EndSwitch
        $j += 1
      WEnd
      Switch $r
        Case -1
          $hi = $mi - 1
        Case  1
          $lo = $mi + 1
        Case  0 ; Equal
          ExitLoop
      EndSwitch
    WEnd
    If $i > $mi Then _ ; Make space for the row number in index
      DllCall( $hKernel32Dll, "none", "RtlMoveMemory", "struct*", $pIndex+($mi+1)*4, "struct*", $pIndex+$mi*4, "ulong_ptr", ($i-$mi)*4 )
    DllStructSetData( $tIndex, 1, $i, $mi+1+($lo=$mi+1) ) ; Insert row number $i at position $mi+1+($lo=$mi+1) in index
  Next
EndFunc

Or you can download this file if you prefer: Sort.au3

 

I have tested how long time the three methods (_ArrayMultiColSort by Melba23, SQLite sort by Chimp, and the method above) takes to sort six arrays with 10,000/50,000 rows and 3/6/9 columns. The arrays are sorted by column 0 (strings), 1 (integers) and 2 (reals). Column 0 and 1 contains a relatively large number of duplicates.

Results for 10,000 rows:

$aItems[10000][3]                      $aItems[10000][6]                      $aItems[10000][9]

Fill array ...                         Fill array ...                         Fill array ...
Fill array ... done                    Fill array ... done                    Fill array ... done

Sort by index ...                      Sort by index ...                      Sort by index ...
Time: 1217.88761269971                 Time: 1248.21605830786                 Time: 1236.41466104082
Sort by index ... done                 Sort by index ... done                 Sort by index ... done

Sort by SQLite ...                     Sort by SQLite ...                     Sort by SQLite ...
Time: 2635.69246331332                 Time: 3543.51988465855                 Time: 4398.68212872624
Sort by SQLite ... done                Sort by SQLite ... done                Sort by SQLite ... done

Sort by _ArrayMultiColSort ...         Sort by _ArrayMultiColSort ...         Sort by _ArrayMultiColSort ...
Time: 1146.7832396923                  Time: 1521.86873177777                 Time: 1831.70970213038
Sort by _ArrayMultiColSort ... done    Sort by _ArrayMultiColSort ... done    Sort by _ArrayMultiColSort ... done

Results for 50,000 rows:

$aItems[50000][3]                      $aItems[50000][6]                      $aItems[50000][9]

Fill array ...                         Fill array ...                         Fill array ...
Fill array ... done                    Fill array ... done                    Fill array ... done

Sort by index ...                      Sort by index ...                      Sort by index ...
Time: 7166.40803514761                 Time: 7174.31887542089                 Time: 7188.0017143575
Sort by index ... done                 Sort by index ... done                 Sort by index ... done

Sort by SQLite ...                     Sort by SQLite ...                     Sort by SQLite ...
Time: 13285.8896390571                 Time: 17742.5454596211                 Time: 21928.3266376507
Sort by SQLite ... done                Sort by SQLite ... done                Sort by SQLite ... done

Sort by _ArrayMultiColSort ...         Sort by _ArrayMultiColSort ...         Sort by _ArrayMultiColSort ...
Time: 6216.31940253656                 Time: 8181.67386319132                 Time: 10040.1219591297
Sort by _ArrayMultiColSort ... done    Sort by _ArrayMultiColSort ... done    Sort by _ArrayMultiColSort ... done

All necessary code to repeat the tests is included in the zip: Sorting.7z. Run Test.au3.

I'm interested in this topic because I need a quick way to sort and maintain (large) arrays in Virtual listviews for huge number of rows.

 

Edited June 16, 2015 by LarsJ

[c.haslam]

Interesting. So SQlite is not the fastest. I will download your scripts.

[jchd]

No, but it can reveal fastest when the sorting conditions become complex, as I examplified before. It certainly is the most flexible approach but this comes at a price. This is a common tradeoff.