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
}
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 . "@r@n"
}
Else {
for k, v in VetG
StOut := StOut . v . ","
StOut := StOut . "@r@n"
If (bG<> 0) {
for k, v in bG
StOut := StOut . v . ","
StOut := StOut . "@r@n"
}
If (cG<>0) {
for k, v in cG
StOut := StOut . v . ","
}
}
MsgBox 0, Example, % StOut
}
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)
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)
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 -
