Sort dense arrays or matrices

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

Sort dense arrays or matrices

30 Apr 2016, 16:50

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 !

17 Apr 2017, 01:52

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
---------------------------

I love your work !
Helgef
Posts: 4693
Joined: 17 Jul 2016, 01:02
Contact:

Re: Sort dense arrays or matrices

22 Apr 2017, 16:20

Good job :thumbup:
You might improve performance by using SetCapacity() 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

28 Apr 2017, 10:21

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

Re: Sort dense arrays or matrices

30 Dec 2018, 11:52

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

30 Dec 2018, 12:04

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

Code: Select all

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

Return to “Scripts and Functions”

Who is online

Users browsing this forum: No registered users and 28 guests