## Sort dense arrays or matrices

Post your working scripts, libraries and tools
paulobuchsbaum
Posts: 13
Joined: 27 Feb 2016, 22:14

### Sort dense arrays or matrices

I've searched in Internet for a good and simple Sort algorithm written in AutoHotkey language for dense arrays or matrices.

I haven't found nothing. So I've developed my own code.

Bubble sort is a common but slow sort algorithm (Execution Time ~ N^2, where N is number of elements).

There are some good sort algorithms (Execution time ~ N Log(N), where N is number of elements). like Heapsort, MergeSort and QuickSort. I've selected QuickSort. It's easy, elegant, and has low memory requirements

This function (QuickSort) sorts one array, allowing specify 1 or more additional arrays, that will be rearranged based on first sorted array.

QuickSort also sort one matrix. The matrices need to have just 2 dimensions and has an additional parameter with the column number that will be sorted.

I hope that it be useful for the community.

Code: Select all

``````;******************************************************************************
;                          QuickSort
; Sort array using QuickSort algorithm
;     ARR - Array to be sorted or Matrix to be sorted (By Column)
;     ASCEND is TRUE if sort is in ascending order
;     *M => VET1,VET2, - Optional arrays of same size to be sorted accordingly
;           or NCOL - Column number in ARR to be sorted if ARR is a matrix
;
; Limitation: Don't check if arrays are sparse arrays.
;             Assume dense arrays or matrices with integer indices starting from 1.
;******************************************************************************
QuickSort(Arr, Ascend = True, M*)
{
Local I, V, Out, L,  Rasc, N, LI, Multi, ComprM, NCol, Ind

if (Arr.Length() <= 1) ; Array with size <= 1 is already sorted
return Arr

If (Not Isobject(Arr))
return "First parameter needs to be a array"

LenM := M.Length()    ; Number of parameters after ASCEND
NCol := 0               ; Assumes initially no matrix
HasOtherArrays := ( LenM > 0 )   ; TRUE if has other arrays or column number

Multi := False
IF HasOtherArrays {
Multi := Not IsObject(M[1])  ; True if ARR is bidimensional
If (Multi) {
NCol := M[1]                 ; Column number of bidimensional array
HasOtherArrays :=  False

If NCol is Not Integer
return "Third parameter needs to be a valid column number"
If (Not IsObject(Arr(1)))
return "First parameter needs to be a multidimensional array"
If ( (NCol<=0) or (NCol > Arr[1].Length()) )
return "Third parameter needs to be a valid column number"
}
}

If (Not Multi)  {
If (IsObject(Arr[1]))
return "If first parameter is a bidimensional array, it demands a column number"
}

LI := 0
N := 0
IF (HasOtherArrays)  {
Loop % LenM {    ; Scan aditional array parameters
Ind := A_INDEX
V := M[Ind]
If (IsObject(V[1]))
return  (Ind+2) . "o. parameter needs to be a single array"
}

LI := 1   ; Assumes 1 as the array/matrix start
N := Arr.Clone()   ; N : Array with same size than Array to be sorted
L := Arr.Length()  ; L : Array Size

Loop % L
N[A_INDEX] := A_INDEX  ; Starts with index number of each element from array
}

; Sort ARR with ASCEND, N is array with elements positions and
;  LI is 1 if has additional arrays to be sorted
;  NCOL is column number to be sorted if ARR is a bidimensional array
Out :=  QuickAux(Arr, Ascend, N, LI, NCol)

; Scan additional arrays storing the original position in sorted array
If (HasOtherArrays)  {
Loop % ComprM {
V := M[A_Index]  ; Current aditional array
Rasc := V.Clone()
Loop % L     ; Put its elements in the sorted order based on position of sorted elements in the original array
V[A_INDEX] := Rasc[N[A_Index]]
}
}

Return Out
}

;=================================================================
;                       QuickAux
; Auxiliary recursive function to make a Quicksort in a array ou matrix
;    ARR - Array or Matrix to be sorted
;    ASCEND - TRUE if sort is ascending
;    N   - Array with original elements position
;    LI  - Position of array ARR in the array from parent recursion
;    NCOL - Column number in Matrix to be sorted. O in array case.
;===================================================================
QuickAux(Arr,Ascend, N, LI, NCol)

{
Local Bef, Aft, Mid
Local Before, Middle, After
Local Pivot, kInd, vElem, LAr, Met
Local LB := 0, LM := 0, LM := 0

LAr := Arr.Length()

if (LAr <= 1)
return Arr

IF (LI>0) {    ; Has Another Arrays
Bef := [],  Aft := [], Mid := []
}

Before := [], Middle := [], After := []

Met := LAr // 2    ; Regarding speed, halfway is the Best pivot element for almost sorted array and matrices

If (NCol > 0)
Pivot := Arr[Met,NCol]
else
Pivot := Arr[Met]  ; PIVOT is Random  element in array

; Classify array elems in 3 groups: Greater than PIVOT, Lower Than PIVOT and equal
for kInd, vElem in Arr     {
if (NCol > 0)
Ch := vElem[NCol]
else
Ch := vElem

if ( Ascend ? Ch < Pivot : Ch > Pivot )  {
Before.Push(vElem)    ; Append vElem at BEFORE
IF (LI>0)             ; if has another arrays
Bef.Push(N[kInd+LI-1])     ; Append index to original element at BEF
} else if ( Ascend ? Ch > Pivot : Ch < Pivot ) {
After.Push(vElem)
IF (LI>0)
Aft.Push(N[kInd+LI-1])
} else  {
Middle.Push(vElem)
IF (LI>0)
Mid.Push(N[kInd+LI-1])
}
}

;  Put pieces of array with index to elements together in N
IF (LI>0) {
LB := Bef.Length()
LM := Mid.Length()
LA := Aft.Length()

Loop % LB
N[LI + A_INDEX - 1] := Bef[A_INDEX]

Loop % LM
N[LI + LB +  A_INDEX - 1] := Mid[A_INDEX]

Loop % LA
N[LI + LB + LM + A_INDEX - 1] := Aft[A_INDEX]
}

; Concat BEFORE, MIDDLE and AFTER Arrays
; BEFORE and AFTER arrays need to be sorted before
; N stores the array position to be sorted in the original array
return Cat(QuickAux(Before,Ascend,N,LI,NCol), Middle, QuickAux(After,Ascend,N,LI+LB+LM,NCol)) ; So Concat the sorted BEFORE, MIDDLE and sorted AFTER arrays
}

;*************************************************************
;                       Cat
; Concat 2 or more arrays or matrices by rows
;**************************************************************
Cat(Vet*)
{
Local VRes := [] , L, i, V
For I , V in Vet {
L := VRes.Length()+1
If ( V.Length() > 0 )
VRes.InsertAt(L,V*)
}
Return VRes
}

;***************************************************************************
;                       CatCol
; Concat 2 or more matrices by columns
; Is a aditional function no used directly in QuickSort, but akin with Cat
;*************************************************************************
CatCol(Vet*)
{
Local VRes := [] , L, I, V, VAux, NLins, NL, Aux, NC, NV, NCD

NVets := Vet.Length()          ; Number of parameters
NLins := Vet[1].Length()       ; Number of rows from matrix

VRes := []

Loop % NLins  {
NL := A_INDEX      ; Current Row
ColAcum := 0
Loop % NVets  {
NV := A_INDEX  ; Current Matrix
NCols := Vet[NV,1].Length()
Loop % NCols  {
NC := A_INDEX  ; Current Column
NCD := A_INDEX + ColAcum   ; Current Column in Destination
Aux := Vet[NV,NL,NC]
VRes[NL,NCD] := Aux
}
ColAcum := ColAcum + NCols
}
}
Return VRes
}
``````
I've made a sample print function, that needs to be placed after the function calls below, just for show the results:

Code: Select all

``````;******************************************************************************************
;                       PrintMat
; Sample for print examples
;*******************************************************************************************
PrintMat(VetG, bG = 0, cG = 0)
{
Local StOut := "", k, v
If IsObject(VetG[1])
for k, v in VetG {
for j, w in v
StOut := StOut . w  . " - "
StOut := StOut . "@[email protected]"
}
Else  {
for k, v in VetG
StOut := StOut . v  . ","
StOut := StOut . "@[email protected]"
If (bG<> 0) {
for k, v in bG
StOut := StOut . v  . ","
StOut := StOut . "@[email protected]"
}
If (cG<>0) {
for k, v in cG
StOut := StOut . v  . ","
}
}
MsgBox 0, Example, % StOut
}
``````
Now we have 2 simples examples:

First Example:

Code: Select all

``````#EscapeChar @   ;  Changes escape character from ' (default) to  @
aG := [2, 3, 1, 5, 4]
bG := ["Butterfly", "Cat","Animal", "Zebra", "Elephant"]
cG := ["B","C", "A","Z","E"]
VetG := QuickSort(aG,False,bG,cG)
PrintMat(VetG,bG,cG)
``````
The inputs:

Input arrays
Ag> 2 - 3 - 1 - 5 - 4 -
Bg> Butterfly - Cat - Animal - Zebra - Elephant
Cg> B - C - A - Z - E

And the results, based on first array, in descending order

Sorted arrays
Ag> 5 - 4 - 3 - 2 - 1 -
Bg> Zebra - Elephant - Cat - Butterfly - Animal -
Cg> Z - E - C - B - A -

Second Example:

Code: Select all

``````#EscapeChar @   ;  Changes escape character from ' (default) to  @
MatG := [ [2, "Animal", "Z" ],  [3, "Elephant", "E" ],  [1, "Cat", "C" ] ,  [5, "Butterfly", "B" ],  [4, "Zebra", "A" ] ]
MatG := QuickSort(MatG,True,2)
PrintMat(MatG)
``````
The input:

Input Matrix
2 - Animal - Z
3 - Elephant - E -
1 - Cat - C -
5 - Butterfly - B
4 - Zebra - A -

And the results, ordered by 2o. column, in ascending order.

Sorted Matrix
2 - Animal - Z
5 - Butterfly - B
1 - Cat - C -
3 - Elephant - E -
4 - Zebra - A -
titep
Posts: 31
Joined: 14 Nov 2015, 09:01

### Error Report !

line 35 should be : If (Not IsObject(Arr[1]))
instead of : If (Not IsObject(Arr(1)))

the example 1 give the result :

---------------------------
Example
---------------------------
5,4,3,2,1,

Butterfly,Cat,Animal,Zebra,Elephant, ———-> is not sorted according to aG,

B,C,A,Z,E, ———-> is not sorted according to aG,
---------------------------
OK
---------------------------

Helgef
Posts: 4693
Joined: 17 Jul 2016, 01:02
Contact:

### Re: Sort dense arrays or matrices

Good job
You might improve performance by using for some arrays, eg,

Code: Select all

``````Before := [], Middle := [], After := []
Before.setcapacity(LAr), Middle.setcapacity(LAr), After.setcapacity(LAr)
``````
For simple array sorting, if you can decide on a delimiter, you can use the built-in sort command, it also gives you quite a few sorting options,

Code: Select all

``````sortArr(arr,opt:=""){
; Sort array using sort options
; https://autohotkey.com/docs/commands/Sort.htm
static guess:=0
if guess
VarSetCapacity(str,arr.length()*guess,0)	; Speed can be improved by making a guess on the needed size.
RegExMatch(opt,"O)\bD(.*?)\b",delimiter) ? delimiter:=delimiter[1] : (delimiter:="`n", opt.=" D`n")
for k, v in arr
str.=v . delimiter
str:=RTrim(str,delimiter)
Sort,str, % opt
return StrSplit(str,delimiter)
}
``````
Thanks for sharing, cheers.
titep
Posts: 31
Joined: 14 Nov 2015, 09:01

### Re: Sort dense arrays or matrices

great ! Helget.
kkleinfelter
Posts: 23
Joined: 21 Dec 2018, 10:59

### Re: Sort dense arrays or matrices

Hmmm... When I run the first example, I get

Code: Select all

``````1,2,3,4,5
Butterfly,Cat,Animal,Zebra,Elephant
B,C,A,Z,E
``````
I'd really like to be able to sort those additional arrays.
kkleinfelter
Posts: 23
Joined: 21 Dec 2018, 10:59

### Re: Sort dense arrays or matrices

Looks like maybe this fixes the code so that Example 1 works:

Code: Select all

``````; BUG FIX - KPK
;	Loop % ComprM {
LOOP % LenM {
``````