# Array 2D Sort/Binary Find on multiple subitems

## Recommended Posts

Hi,

here is a array 2D sorting function, using multiple subitems as sorting criteria
(for example : to sort the lines of a 2D array from the content of the columns 1, 5 and 3 with this order of priority)
-> This is the function ARRAY_2D_SORT_MULTISUBITEMS(\$arr, \$i_start, \$i_end, \$arr_sorting, \$i_sorted_dim),
which returns the sorted array

ONCE a 2D array range (\$i_start to \$i_end) is sorted with a given set of criteria, it can be BINARY searched with the SAME criteria
(however the criteria can be cut : with the previous example you could search all items with "blob" in column 1 and "test" on column 5)
-> This is the function ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS(\$arr, \$i_start, \$i_end, \$arr_searching, \$i_searched_dim),
which returns all matching items indexes

As an example on how to use them, these 2 main functions are included in a working script.
(it's quite difficult to explain with words what is a 2D sorting/searching with multiple criteria,
so the example script gives a good visual explanation of these operations)

Usage Note :
* Each dimension, 1 or 2, can be sorted, the other dimension (that I call the sorting dimension) being used to perform the sort
* Each sort/search criterion in the sorting dimension has its own [ascending/descending] and [case sensitive/not case sensitive] options
* All the criteria are passed via the 2D arrays \$arr_sorting, and \$arr_searching, which basically are the same, except that :
-> the \$arr_sorting does not need the [searching value] & [disable flag] columns, which are only used for searching,
if these columns exist they are IGNORED when SORTING (especially the [disable flag])
-> the \$arr_searching can have some of the last criteria removed
by setting a [disable flag] to True on an index, which will also disable the following ones
* Sorting/binary searching does NOT like to have a mix of numbers and strings in the same sorting line/column
(I don't know the result for such an array, but you could have [30, "6", 9] when sorted ascendingly !)

Technical note :
* The sorting function uses the InsertSort and QuickSort methods found in the Array udf.
* But the sorting function also uses a VIRTUAL SORTING method
(more efficient if the array has a lot of subitems, i.e. a large sorting dimension),
'virtual' meaning that the items in the sorted array are not swapped until the sorting has completed,
instead their original indexes are redirected via the \$arr_storedin array.
* The sorting function has a STABLE SORT option, which means that items that do not need to be swapped can have their order preserved
stable sort increases processing time by about 15-20%

Code for 2D arrays :

```AutoItSetOption("MustDeclareVars", 1)

MAIN()

Func MAIN()
Local \$b_isnum, \$i_searched_size, \$i_searched_dim, \$i_speed_size, \$b_stablesort

\$i_searched_size = \$i_searched_size
\$i_searched_dim = \$i_searched_dim
\$i_speed_size = \$i_speed_size

\$b_stablesort = True
\$b_stablesort = False

\$b_isnum = True
\$b_isnum = False

\$i_searched_size = 25
\$i_searched_dim = 1
TEST_SORT_BINFIND(\$i_searched_size, \$b_isnum, \$i_searched_dim, \$b_stablesort)

; for 1000 items items (and 3 columns) :
; 0.36s for numbers (0.40s with stable sort), 0.41s for strings (0.46s with stable sort), on my old computer
\$i_speed_size = 1000
TEST_SORT_SPEED(\$i_speed_size, \$b_isnum, \$b_stablesort)
EndFunc

Func TEST_SORT_BINFIND(\$i_searched_size, \$b_isnum, \$i_searched_dim, \$b_stablesort)
Local \$i_msg, \$s_res, \$b_newarr, \$b_ressort, \$i_maxindex_sorting_dim, \$s_i, \$i
Local \$arr, \$arr_bak, \$arr_searching, \$arr_found, \$arr_acc

Local Const \$h_gui = GUICreate("ARRAY_2D SORT & BINARY FIND", 800, 700, Default, Default, BitOR(0x00040000, 0x00020000))
Local Const \$id_edit = GUICtrlCreateEdit("", 5, 5, 790, 645, BitOR(0x800, 0x00100000, 0x00200000))
GUICtrlSetResizing(Default, 102)
GUICtrlSetFont(Default, 9, 400, 0, "courier new")
Local Const \$id_button_newarr = GUICtrlCreateButton("&New Array (F5)", 5, 655, 120, 20, 0x1)
GUICtrlSetResizing(Default, 66 + 768)
Local Const \$id_button_swap = GUICtrlCreateButton("&Swap Dim", 140, 655, 120, 20)
GUICtrlSetResizing(Default, 66 + 768)
Local Const \$id_button_resort = GUICtrlCreateButton("&Re-Sort Array (F6)", 670, 655, 120, 20)
GUICtrlSetResizing(Default, 68 + 768)
GUICtrlSetTip(Default, _
"Basic Quicksort is not 'stable' by itself," & @CR & _
"so identical (according to the criterion(s)) items" & @CR & _
"can be swapped after a re-sort action" & @CR & _
@CR & _
"But if \$b_stablesort is set to True" & @CR & _
"original order between identical items is preserved" & @CR & _
"(increases processing time by ~10-20%)")

Dim \$arr_acc[2][2] = [ _
["{F5}", \$id_button_newarr], _
["{F6}", \$id_button_resort] _
]
GUISetAccelerators(\$arr_acc, \$h_gui)
GUISetState(@SW_SHOW, \$h_gui)

; test code for sort & search dim 1 or 2
\$b_newarr = True
While True
If \$b_newarr Then
; random array create
\$i_maxindex_sorting_dim = 3
If \$i_searched_dim = 1 Then
Dim \$arr[\$i_searched_size][\$i_maxindex_sorting_dim]
For \$i = 0 To UBound(\$arr, \$i_searched_dim) - 1
If \$b_isnum Then
\$arr[\$i][0] = Random(-1, 1, 1)
\$arr[\$i][1] = Random(-9, 9, 1)
\$arr[\$i][2] = Random(-1, 1, 1)
Else
\$arr[\$i][0] = MAKE_STRING("a", "c", 1)
\$arr[\$i][1] = Random(-9, 9, 1)
\$arr[\$i][2] = MAKE_STRING("a", "c", 1)
EndIf
Next
Else
Dim \$arr[\$i_maxindex_sorting_dim][\$i_searched_size]
For \$i = 0 To UBound(\$arr, \$i_searched_dim) - 1
If \$b_isnum Then
\$arr[0][\$i] = Random(-1, 1, 1)
\$arr[1][\$i] = Random(-9, 9, 1)
\$arr[2][\$i] = Random(-1, 1, 1)
Else
\$arr[0][\$i] = MAKE_STRING("a", "c", 1)
\$arr[1][\$i] = Random(-9, 9, 1)
\$arr[2][\$i] = MAKE_STRING("a", "c", 1)
EndIf
Next
EndIf
\$arr_bak = \$arr
EndIf

; \$arr_sorting and \$arr_searching must be the same array (but sorting only would not require value searched & disable_flag columns)
; sort/search criterion : [sorting index, ascending, case sensitive, value searched, disabled flag]
If \$b_isnum Then
Dim \$arr_searching[2][5] = [[2, False, False, 1, False], [0, True, False, 0, False]]
Else
Dim \$arr_searching[2][5] = [[2, False, False, "c", False], [0, True, False, "B", False]]
EndIf

; \$i_searched_dim must be the same for sort & search, searched range (\$i_start to \$i_end) must be sorted before searching
\$b_ressort = ARRAY_2D_SORT_MULTISUBITEMS(\$arr, 0, UBound(\$arr, \$i_searched_dim) - 1, \$arr_searching, \$i_searched_dim, \$b_stablesort)
\$arr_found = ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS(\$arr, 0, UBound(\$arr, \$i_searched_dim) - 1, \$arr_searching, \$i_searched_dim)

\$s_res = ""
If \$i_searched_dim = 1 Then
For \$i = 0 To UBound(\$arr, 1) - 1
\$s_i = \$i
If \$i < 10 Then \$s_i = "0" & \$i
\$s_res = \$s_res & \$s_i & " :" & @TAB
For \$j = 0 To UBound(\$arr_bak, 2) - 1
If StringLen(\$arr_bak[\$i][\$j]) < 2 Then \$s_res = \$s_res & " "
\$s_res = \$s_res & \$arr_bak[\$i][\$j] & "|"
Next
\$s_res = \$s_res & @TAB
For \$j = 0 To UBound(\$arr, 2) - 1
If StringLen(\$arr[\$i][\$j]) < 2 Then \$s_res = \$s_res & " "
\$s_res = \$s_res & \$arr[\$i][\$j] & "|"
Next
For \$j = 1 To UBound(\$arr_found) - 1
If \$arr_found[\$j] = \$i Then
\$s_res = \$s_res & "+"
ExitLoop
EndIf
Next
\$s_res = \$s_res & @CRLF
Next
\$s_res = \$s_res & "sorted" & @TAB & " original" & @TAB & "  array  found(+)" & @CRLF
\$s_res = \$s_res & "indexes" & @TAB & "  array" & @TAB & @TAB & "  sorted" & @CRLF
Else
For \$i = 0 To UBound(\$arr, 2) - 1
\$s_i = \$i
If \$i < 10 Then \$s_i = "0" & \$i
\$s_res = \$s_res & \$s_i & "|"
Next
\$s_res = \$s_res & " -> sorted indexes" & @CRLF & @CRLF
For \$i = 0 To UBound(\$arr_bak, 1) - 1
For \$j = 0 To UBound(\$arr_bak, 2) - 1
If StringLen(\$arr_bak[\$i][\$j]) < 2 Then \$s_res = \$s_res & " "
\$s_res = \$s_res & \$arr_bak[\$i][\$j] & "|"
Next
If \$i = 0 Then \$s_res = \$s_res & " -> original array"
\$s_res = \$s_res & @CRLF
Next
\$s_res = \$s_res & @CRLF & @CRLF
For \$i = 0 To UBound(\$arr, 1) - 1
For \$j = 0 To UBound(\$arr, 2) - 1
If StringLen(\$arr[\$i][\$j]) < 2 Then \$s_res = \$s_res & " "
\$s_res = \$s_res & \$arr[\$i][\$j] & "|"
Next
If \$i = 0 Then \$s_res = \$s_res & " -> array sorted"
\$s_res = \$s_res & @CRLF
Next
For \$i = 0 To UBound(\$arr, 2) - 1
For \$j = 1 To UBound(\$arr_found) - 1
If \$arr_found[\$j] = \$i Then
\$s_res = \$s_res & " +|"
ExitLoop
EndIf
Next
If \$j = UBound(\$arr_found) Then \$s_res = \$s_res & "  |"
Next
\$s_res = \$s_res & " -> found(+)" & @CRLF
EndIf
\$s_res = \$s_res & @CRLF

\$s_res = \$s_res & "Array is displayed as arr[line][column] (so Dim 1 is showed as lines, and Dim 2 as columns)" & @CRLF & @CRLF
\$s_res = \$s_res & "Array sorted : " & \$b_ressort & ", Stable sort : " & \$b_stablesort & @CRLF
\$s_res = \$s_res & "Sorted & searched Dim : " & \$i_searched_dim & " (displayed as "

If \$i_searched_dim = 1 Then
\$s_res = \$s_res & "lines), searching indexes are on the other Dim" & @CRLF & @CRLF
Else
\$s_res = \$s_res & "columns), searching indexes are on the other Dim" & @CRLF & @CRLF
EndIf
\$s_res = \$s_res & "Sorting & searching array criterion(s) (V highest to lowest priority V) :" & @CRLF
For \$i = 0 To UBound(\$arr_searching, 1) - 1
\$s_res = \$s_res & _
"Num:" & \$i & " | " & _
"Searching index:" & \$arr_searching[\$i][0] & " | " & _
"Ascending:" & \$arr_searching[\$i][1] & " | " & _
"Casesens:" & \$arr_searching[\$i][2] & " | " & _
"Searching value:" & \$arr_searching[\$i][3] & " | " & _
"Disabled flag:" & \$arr_searching[\$i][4]
\$s_res = \$s_res & @CRLF
Next
\$s_res = \$s_res & @CRLF

\$s_res = \$s_res & \$arr_found[0] & " searched indexes found : "
For \$i = 1 To UBound(\$arr_found) - 1
\$s_res = \$s_res & \$arr_found[\$i]
If \$i < UBound(\$arr_found) - 1 Then \$s_res = \$s_res & " | "
Next
\$s_res = \$s_res & @CRLF

GUICtrlSetData(\$id_edit, \$s_res)
While True
\$i_msg = GUIGetMsg()
If \$i_msg = -3 Then
GUISetState(@SW_HIDE, \$h_gui)
Return
EndIf
If \$i_msg = \$id_button_newarr Then
\$b_newarr = True
ExitLoop
EndIf
If \$i_msg = \$id_button_resort Then
\$b_newarr = False
ExitLoop
EndIf
If \$i_msg = \$id_button_swap Then
\$b_newarr = True
If \$i_searched_dim = 1 Then
\$i_searched_dim = 2
Else
\$i_searched_dim = 1
EndIf
ExitLoop
EndIf
WEnd
WEnd
EndFunc

Func TEST_SORT_SPEED(\$i_speed_size, \$b_isnum, \$b_stablesort)
Local \$d_timer, \$i_ms_timerdiff, \$b_ressort, \$s_text, \$i_maxindex_sorting_dim
Local \$arr, \$arr_sorting

\$i_maxindex_sorting_dim = 3
Dim \$arr[\$i_speed_size][\$i_maxindex_sorting_dim]

Do
ToolTip(@CR & " Speed test... " & @CR)
For \$i = 0 To UBound(\$arr, 1) - 1
If \$b_isnum Then
\$arr[\$i][0] = Random(0, 0x7FFFFFFF, 1)
\$arr[\$i][1] = Random(-9, 9, 1)
\$arr[\$i][2] = Random(0, 0x7FFFFFFF, 1)
Else
\$arr[\$i][0] = Hex(Random(0, 0x7FFFFFFF, 1))
\$arr[\$i][1] = Random(-9, 9, 1)
\$arr[\$i][2] = Hex(Random(0, 0x7FFFFFFF, 1))
EndIf
Next

; change this array to change the sort
Dim \$arr_sorting[2][3] = [[2, False, False], [0, True, False]]

\$d_timer = TimerInit()
\$b_ressort = ARRAY_2D_SORT_MULTISUBITEMS(\$arr, 0, UBound(\$arr, 1) - 1, \$arr_sorting, 1, \$b_stablesort)
\$i_ms_timerdiff = TimerDiff(\$d_timer)

\$s_text = (\$i_ms_timerdiff / 1000) & " s for " & \$i_speed_size & " sorted lines and " & \$i_maxindex_sorting_dim & " columns" & @CRLF
If \$b_isnum Then
\$s_text = \$s_text & "with numbers"
Else
\$s_text = \$s_text & "with strings"
EndIf
\$s_text = \$s_text & ", Stable sort : " & \$b_stablesort & @CRLF & @CRLF

\$s_text = \$s_text & "Sorting array criterion(s) (V highest to lowest priority V) :" & @CRLF
For \$i = 0 To UBound(\$arr_sorting, 1) - 1
\$s_text = \$s_text & _
"Num:" & \$i & " | " & _
"Sorting index:" & \$arr_sorting[\$i][0] & " | " & _
"Ascending:" & \$arr_sorting[\$i][1] & " | " & _
"Casesens:" & \$arr_sorting[\$i][2]
\$s_text = \$s_text & @CRLF
Next

ToolTip("")
Until MsgBox(5 + 64 + 4096, "Sorted : " & \$b_ressort, \$s_text) <> 4
EndFunc

Func MAKE_STRING(\$s_char_1, \$s_char_2, \$i_len)
Local \$s_res, \$i_char_1, \$i_char_2

\$i_char_1 = Asc(StringLower(\$s_char_1))
\$i_char_2 = Asc(StringLower(\$s_char_2))

\$s_res = ""
For \$i = 1 To \$i_len
If Random(0, 1, 1) = 0 Then
\$s_res = \$s_res & StringUpper(Chr(Random(\$i_char_1, \$i_char_2, 1)))
Else
\$s_res = \$s_res & Chr(Random(\$i_char_1, \$i_char_2, 1))
EndIf
Next
Return \$s_res
EndFunc

; **************************************************************************************************
; End of example script, beginning of reusable functions *******************************************
; **************************************************************************************************

; Arrays 2D ****************************************************************************************
; function always returns a 1D array, on success containing the indexes of the found item(s)
; if n items found : [n, index_1, ... index_n] (n+1 slots array, the first slot gives the number of items found)
; if no item found (possibly \$i_end < \$i_start) : [0] (one slot array), on input error : [-1] (one slot array)
;
; \$i_searched_dim : dimension (can be 1 or 2) that will be i_searched_dim in the 2D array \$arr
; \$arr_searching[0..(n-1)][0] : n indexes (on the other dim, the \$i_searching_dim) used to search \$i_searched_dim
; \$arr_searching[0..(n-1)][1] : ascending (True) or descending (False), for each index
; \$arr_searching[0..(n-1)][2] : case sensitive (True) or NOT case-sensitive (False), for each index
; \$arr_searching[0..(n-1)][3] : searching value, for each index
; \$arr_searching[0..(n-1)][4] : disable flag (True = disabled index, False = enabled index)
;   the same index can not be used twice
;   if an index is DISABLED all FOLLOWING indexes will also be DISABLED
;   if the FIRST index is DISABLED then ALL \$i_searched_dim indexes in \$arr are returned
;
;   array's searching indexes MUST BE SORTED BEFORE binary searching
;   (in the direction defined by \$arr_searching[0..(n-1)][1], and with the case defined by \$arr_searching[0..(n-1)][2])
;   or function may return less matching items (possibly none) than there are !
;
;   the var TYPE (number or string) of \$arr_searching[0..(n-1)][3] sets the type of comparison (as numbers or strings) done for this index
Func ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS(ByRef \$arr, \$i_start, \$i_end, \$arr_searching, \$i_searched_dim)
Local \$i_searching_index, \$i_maxindex_searching_arr, \$i_searching_dim, \$i, \$j
Local \$b_dim_1_searched, \$b_hasdisabled, \$s_indexes_found, \$i_respos, \$i_mid
Local \$arr_err, \$arr_none
Local Const \$i_stringcomp_casesens      = 1
Local Const \$i_stringcomp_not_casesens  = 2
; searching index = 0; ascending = 1; casesens to casecomp = 2; searching value = 3; disable = 4

Dim \$arr_err[1] = [-1]
Dim \$arr_none[1] = [0]

If Not(IsArray(\$arr)) Then Return \$arr_err
If Not(IsArray(\$arr_searching)) Then Return \$arr_err
Switch \$i_searched_dim
Case 1
\$i_searching_dim = 2
\$b_dim_1_searched = True
Case 2
\$i_searching_dim = 1
\$b_dim_1_searched = False
Case Else
Return \$arr_err
EndSwitch
If UBound(\$arr, 0) <> 2 Then Return \$arr_err
If UBound(\$arr_searching, 0) <> 2 Then Return \$arr_err
If UBound(\$arr_searching, 1) > UBound(\$arr, \$i_searching_dim) Then Return \$arr_err
If UBound(\$arr_searching, 2) < 5 Then Return \$arr_err
\$b_hasdisabled = False
For \$i = 0 To (UBound(\$arr_searching, 1) - 1)
\$i_searching_index = \$arr_searching[\$i][0]
If \$i_searching_index < 0 Or \$i_searching_index > (UBound(\$arr, \$i_searching_dim) - 1) Then Return \$arr_err
For \$j = 0 To (\$i - 1)
If \$arr_searching[\$j][0] = \$i_searching_index Then Return \$arr_err
Next
If \$arr_searching[\$i][2] Then
\$arr_searching[\$i][2] = \$i_stringcomp_casesens
Else
\$arr_searching[\$i][2] = \$i_stringcomp_not_casesens
EndIf
If \$b_hasdisabled Then
\$arr_searching[\$i][4] = True
ElseIf \$arr_searching[\$i][4] Then
\$b_hasdisabled = True
EndIf
Next

If \$i_start < 0 Then \$i_start = 0
If \$i_end > (UBound(\$arr, \$i_searched_dim) - 1) Then \$i_end = UBound(\$arr, \$i_searched_dim) - 1
If \$i_end < \$i_start Then Return \$arr_none

\$i_maxindex_searching_arr = UBound(\$arr_searching, 1) - 1

; off-limits test
\$i_respos = ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS_POS(\$arr, \$arr_searching, \$i_maxindex_searching_arr, \$b_dim_1_searched, \$i_start)
If \$i_respos > 0 Then Return \$arr_none
\$i_respos = ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS_POS(\$arr, \$arr_searching, \$i_maxindex_searching_arr, \$b_dim_1_searched, \$i_end)
If \$i_respos < 0 Then Return \$arr_none

Do
; mid test
\$i_mid = Int((\$i_start + \$i_end) / 2)
\$i_respos = ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS_POS(\$arr, \$arr_searching, \$i_maxindex_searching_arr, \$b_dim_1_searched, \$i_mid)

; 1 item found, find others
If \$i_respos = 0 Then
\$s_indexes_found = \$i_mid
For \$i = (\$i_mid - 1) To \$i_start Step -1
\$i_respos = ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS_POS(\$arr, \$arr_searching, \$i_maxindex_searching_arr, \$b_dim_1_searched, \$i)
If \$i_respos <> 0 Then ExitLoop
\$s_indexes_found = \$i & "," & \$s_indexes_found
Next
For \$i = (\$i_mid + 1) To \$i_end
\$i_respos = ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS_POS(\$arr, \$arr_searching, \$i_maxindex_searching_arr, \$b_dim_1_searched, \$i)
If \$i_respos <> 0 Then ExitLoop
\$s_indexes_found = \$s_indexes_found & "," & \$i
Next
Return StringSplit(\$s_indexes_found, ",")
EndIf

; change borders
If \$i_respos > 0 Then
\$i_end = \$i_mid - 1
Else
\$i_start = \$i_mid + 1
EndIf
Until \$i_start > \$i_end

Return \$arr_none
EndFunc

; Internal sub without error checking !
; function returns 0, 1, or -1 : 1 if \$i_tested_index is after searching item, -1 if before, 0 if equal
Func ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS_POS(ByRef \$arr, ByRef \$arr_searching, _
\$i_maxindex_searching_arr, \$b_dim_1_searched, \$i_tested_index)
Local \$i_searching_index, \$b_ascending, \$i_casecomp, \$v_searching, \$v_tested, \$i_rescomp, \$i_sortnum
; searching index = 0; ascending = 1; casecomp = 2; searching value = 3; disable = 4

For \$i_sortnum = 0 To \$i_maxindex_searching_arr
If \$arr_searching[\$i_sortnum][4] Then ExitLoop

\$i_searching_index  = \$arr_searching[\$i_sortnum][0]
\$b_ascending        = \$arr_searching[\$i_sortnum][1]
\$i_casecomp         = \$arr_searching[\$i_sortnum][2]
\$v_searching        = \$arr_searching[\$i_sortnum][3]

If \$b_dim_1_searched Then
\$v_tested = \$arr[\$i_tested_index][\$i_searching_index]
Else
\$v_tested = \$arr[\$i_searching_index][\$i_tested_index]
EndIf

If IsNumber(\$v_searching) Then
If ((\$b_ascending And \$v_tested > \$v_searching) Or (Not(\$b_ascending) And \$v_tested < \$v_searching)) Then Return 1
If ((\$b_ascending And \$v_tested < \$v_searching) Or (Not(\$b_ascending) And \$v_tested > \$v_searching)) Then Return -1
Else
\$i_rescomp = StringCompare(\$v_tested, \$v_searching, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp > 0) Or (Not(\$b_ascending) And \$i_rescomp < 0)) Then Return 1
If ((\$b_ascending And \$i_rescomp < 0) Or (Not(\$b_ascending) And \$i_rescomp > 0)) Then Return -1
EndIf
Next
Return 0
EndFunc

; function returns True (possibly \$i_end <= \$i_start), or False on input error
; \$i_sorted_dim : dimension (can be 1 or 2) that will be sorted in the 2D array \$arr
; \$arr_sorting[0..(n-1)][0] : n indexes (on the other dim, the \$i_sorting_dim) used to sort \$i_sorted_dim
; \$arr_sorting[0..(n-1)][1] : ascending (True) or descending (False), for each index
; \$arr_sorting[0..(n-1)][2] : case sensitive (True) or NOT case-sensitive (False), for each index
; \$arr_sorting[0..(n-1)][3] : not needed, not used (only for ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS searching value)
; \$arr_sorting[0..(n-1)][4] : not needed, not used (only for ARRAY_2D_BINARY_FINDALL_MULTISUBITEMS disable flag)
;   the same index can not be used twice
; \$b_stablesort : if True, with some time cost, preserve order of identical (according to the sorting criterion(s)) items
Func ARRAY_2D_SORT_MULTISUBITEMS(ByRef \$arr, \$i_start, \$i_end, \$arr_sorting, \$i_sorted_dim, \$b_stablesort)
Local \$i_sorting_index, \$i_sorting_dim, \$b_dim_1_sorted, \$i_sortnum, \$i, \$j
Local \$v_first, \$v_tested, \$i_maxindex_sorting_arr
Local \$arr_tmp, \$arr_storedin
Local Const \$i_stringcomp_casesens      = 1
Local Const \$i_stringcomp_not_casesens  = 2
; sorting index = 0; ascending = 1; casesens to casecomp = 2

If Not(IsArray(\$arr)) Then Return False
If Not(IsArray(\$arr_sorting)) Then Return False
Switch \$i_sorted_dim
Case 1
\$i_sorting_dim = 2
\$b_dim_1_sorted = True
Case 2
\$i_sorting_dim = 1
\$b_dim_1_sorted = False
Case Else
Return False
EndSwitch
If UBound(\$arr, 0) <> 2 Then Return False
If UBound(\$arr_sorting, 0) <> 2 Then Return False
If UBound(\$arr_sorting, 1) > UBound(\$arr, \$i_sorting_dim) Then Return False
If UBound(\$arr_sorting, 2) < 3 Then Return False
For \$i = 0 To (UBound(\$arr_sorting, 1) - 1)
\$i_sorting_index = \$arr_sorting[\$i][0]
If \$i_sorting_index < 0 Or \$i_sorting_index > (UBound(\$arr, \$i_sorting_dim) - 1) Then Return False
For \$j = 0 To (\$i - 1)
If \$arr_sorting[\$j][0] = \$i_sorting_index Then Return False
Next
If \$arr_sorting[\$i][2] Then
\$arr_sorting[\$i][2] = \$i_stringcomp_casesens
Else
\$arr_sorting[\$i][2] = \$i_stringcomp_not_casesens
EndIf
Next

If \$i_start < 0 Then \$i_start = 0
If \$i_end > (UBound(\$arr, \$i_sorted_dim) - 1) Then \$i_end = UBound(\$arr, \$i_sorted_dim) - 1
If \$i_end <= \$i_start Then Return True

; init virtual sort : \$arr_storedin[\$i] gives the index in \$arr where the item \$i is currently stored
Dim \$arr_storedin[UBound(\$arr, \$i_sorted_dim)]
For \$i = \$i_start To \$i_end
\$arr_storedin[\$i] = \$i
Next

\$i_maxindex_sorting_arr = UBound(\$arr_sorting, 1) - 1

If \$i_sorted_dim = 1 Then
ARRAY_2D_SORT_MULTISUBITEMS_DOSORT(\$arr, \$arr_sorting, \$arr_storedin, _
\$i_start, \$i_end, \$i_maxindex_sorting_arr, True)
Else
ARRAY_2D_SORT_MULTISUBITEMS_DOSORT(\$arr, \$arr_sorting, \$arr_storedin, _
\$i_start, \$i_end, \$i_maxindex_sorting_arr, False)
EndIf

; stable sort option : re-order ascendingly \$arr_storedin indexes pointing to
; identical (according to the sorting criterion(s)) items
If \$b_stablesort Then
\$i = \$i_start
While \$i < \$i_end
\$j = \$i + 1
While \$j <= \$i_end
For \$i_sortnum = 0 To \$i_maxindex_sorting_arr
\$i_sorting_index = \$arr_sorting[\$i_sortnum][0]

If \$b_dim_1_sorted Then
\$v_first = \$arr[\$arr_storedin[\$i]][\$i_sorting_index]
\$v_tested = \$arr[\$arr_storedin[\$j]][\$i_sorting_index]
Else
\$v_first = \$arr[\$i_sorting_index][\$arr_storedin[\$i]]
\$v_tested = \$arr[\$i_sorting_index][\$arr_storedin[\$j]]
EndIf

If (IsNumber(\$v_first) And IsNumber(\$v_tested)) Then
If \$v_first <> \$v_tested Then ExitLoop(2)
Else
If StringCompare(\$v_first, \$v_tested, \$arr_sorting[\$i_sortnum][2]) <> 0 Then ExitLoop(2)
EndIf
Next
\$j = \$j + 1
WEnd
ARR_SORT_INDEXES(\$arr_storedin, \$i, \$j - 1)
\$i = \$j
WEnd
EndIf

; apply virtual sort
\$arr_tmp = \$arr
If \$b_dim_1_sorted Then
For \$i = \$i_start To \$i_end
For \$j = 0 To (UBound(\$arr, \$i_sorting_dim) - 1)
\$arr[\$i][\$j] = \$arr_tmp[\$arr_storedin[\$i]][\$j]
Next
Next
Else
For \$i = \$i_start To \$i_end
For \$j = 0 To (UBound(\$arr, \$i_sorting_dim) - 1)
\$arr[\$j][\$i] = \$arr_tmp[\$j][\$arr_storedin[\$i]]
Next
Next
EndIf

Return True
EndFunc

; Internal sub without error checking !
; If \$b_dim_1_sorted : dimension 1 is sorted (w. dimension 2 as criterion(s)), else dimension 2 is sorted (w. dimension 1 as criterion(s))
; virtual sorting is done : items in \$arr are not swapped, instead indexes are swapped in \$arr_storedin
Func ARRAY_2D_SORT_MULTISUBITEMS_DOSORT(ByRef \$arr, ByRef \$arr_sorting, ByRef \$arr_storedin, _
\$i_start, \$i_end, \$i_maxindex_sorting_arr, \$b_dim_1_sorted)
Local \$i_left, \$i_right, \$i_rescomp, \$v_pivot, \$v_tested, \$i_pivot, \$i_swap, \$i_sortnum, \$i, \$j
Local \$i_sorting_index, \$b_ascending, \$i_casecomp
Local Const \$i_ins_sort_2d = 10
; sorting index = 0; ascending = 1; casecomp = 2

If \$i_end <= \$i_start Then Return

; InsertionSort (faster for smaller segments)
If (\$i_end - \$i_start) <= \$i_ins_sort_2d Then
For \$i = (\$i_start + 1) To \$i_end
\$i_pivot = \$arr_storedin[\$i]

For \$j = (\$i - 1) To \$i_start Step -1
For \$i_sortnum = 0 To \$i_maxindex_sorting_arr
\$i_sorting_index    = \$arr_sorting[\$i_sortnum][0]
\$b_ascending        = \$arr_sorting[\$i_sortnum][1]
\$i_casecomp         = \$arr_sorting[\$i_sortnum][2]

If \$b_dim_1_sorted Then
\$v_pivot = \$arr[\$i_pivot][\$i_sorting_index]
\$v_tested = \$arr[\$arr_storedin[\$j]][\$i_sorting_index]
Else
\$v_pivot = \$arr[\$i_sorting_index][\$i_pivot]
\$v_tested = \$arr[\$i_sorting_index][\$arr_storedin[\$j]]
EndIf

If (IsNumber(\$v_pivot) And IsNumber(\$v_tested)) Then
If ((\$b_ascending And \$v_pivot > \$v_tested) Or (Not(\$b_ascending) And \$v_pivot < \$v_tested)) Then ExitLoop(2)
If ((\$b_ascending And \$v_pivot < \$v_tested) Or (Not(\$b_ascending) And \$v_pivot > \$v_tested)) Then ExitLoop
Else
\$i_rescomp = StringCompare(\$v_pivot, \$v_tested, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp > 0) Or (Not(\$b_ascending) And \$i_rescomp < 0)) Then ExitLoop(2)
If ((\$b_ascending And \$i_rescomp < 0) Or (Not(\$b_ascending) And \$i_rescomp > 0)) Then ExitLoop
EndIf
If \$i_sortnum >= \$i_maxindex_sorting_arr Then ExitLoop(2)
Next
\$arr_storedin[\$j + 1] = \$arr_storedin[\$j]
Next
\$arr_storedin[\$j + 1] = \$i_pivot
Next
Return
EndIf

; QuickSort
\$i_left = \$i_start
\$i_right = \$i_end
\$i_pivot = \$arr_storedin[Int((\$i_start + \$i_end) / 2)]
Do
While True
For \$i_sortnum = 0 To \$i_maxindex_sorting_arr
\$i_sorting_index    = \$arr_sorting[\$i_sortnum][0]
\$b_ascending        = \$arr_sorting[\$i_sortnum][1]
\$i_casecomp         = \$arr_sorting[\$i_sortnum][2]

If \$b_dim_1_sorted Then
\$v_pivot = \$arr[\$i_pivot][\$i_sorting_index]
\$v_tested = \$arr[\$arr_storedin[\$i_left]][\$i_sorting_index]
Else
\$v_pivot = \$arr[\$i_sorting_index][\$i_pivot]
\$v_tested = \$arr[\$i_sorting_index][\$arr_storedin[\$i_left]]
EndIf

If (IsNumber(\$v_pivot) And IsNumber(\$v_tested)) Then
If ((\$b_ascending And \$v_tested > \$v_pivot) Or (Not(\$b_ascending) And \$v_tested < \$v_pivot)) Then ExitLoop(2)
If ((\$b_ascending And \$v_tested < \$v_pivot) Or (Not(\$b_ascending) And \$v_tested > \$v_pivot)) Then
\$i_left = \$i_left + 1
ExitLoop
EndIf
Else
\$i_rescomp = StringCompare(\$v_tested, \$v_pivot, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp > 0) Or (Not(\$b_ascending) And \$i_rescomp < 0)) Then ExitLoop(2)
If ((\$b_ascending And \$i_rescomp < 0) Or (Not(\$b_ascending) And \$i_rescomp > 0)) Then
\$i_left = \$i_left + 1
ExitLoop
EndIf
EndIf
If \$i_sortnum >= \$i_maxindex_sorting_arr Then ExitLoop(2)
Next
WEnd
While True
For \$i_sortnum = 0 To \$i_maxindex_sorting_arr
\$i_sorting_index    = \$arr_sorting[\$i_sortnum][0]
\$b_ascending        = \$arr_sorting[\$i_sortnum][1]
\$i_casecomp         = \$arr_sorting[\$i_sortnum][2]

If \$b_dim_1_sorted Then
\$v_pivot = \$arr[\$i_pivot][\$i_sorting_index]
\$v_tested = \$arr[\$arr_storedin[\$i_right]][\$i_sorting_index]
Else
\$v_pivot = \$arr[\$i_sorting_index][\$i_pivot]
\$v_tested = \$arr[\$i_sorting_index][\$arr_storedin[\$i_right]]
EndIf

If (IsNumber(\$v_pivot) And IsNumber(\$v_tested)) Then
If ((\$b_ascending And \$v_tested < \$v_pivot) Or (Not(\$b_ascending) And \$v_tested > \$v_pivot)) Then ExitLoop(2)
If ((\$b_ascending And \$v_tested > \$v_pivot) Or (Not(\$b_ascending) And \$v_tested < \$v_pivot)) Then
\$i_right = \$i_right - 1
ExitLoop
EndIf
Else
\$i_rescomp = StringCompare(\$v_tested, \$v_pivot, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp < 0) Or (Not(\$b_ascending) And \$i_rescomp > 0)) Then ExitLoop(2)
If ((\$b_ascending And \$i_rescomp > 0) Or (Not(\$b_ascending) And \$i_rescomp < 0)) Then
\$i_right = \$i_right - 1
ExitLoop
EndIf
EndIf
If \$i_sortnum >= \$i_maxindex_sorting_arr Then ExitLoop(2)
Next
WEnd

; Swap
If \$i_left <= \$i_right Then
\$i_swap = \$arr_storedin[\$i_left]
\$arr_storedin[\$i_left] = \$arr_storedin[\$i_right]
\$arr_storedin[\$i_right] = \$i_swap
\$i_left = \$i_left + 1
\$i_right = \$i_right - 1
EndIf
Until \$i_left > \$i_right

ARRAY_2D_SORT_MULTISUBITEMS_DOSORT(\$arr, \$arr_sorting, \$arr_storedin, _
\$i_start, \$i_right, \$i_maxindex_sorting_arr, \$b_dim_1_sorted)
ARRAY_2D_SORT_MULTISUBITEMS_DOSORT(\$arr, \$arr_sorting, \$arr_storedin, _
\$i_left, \$i_end, \$i_maxindex_sorting_arr, \$b_dim_1_sorted)
EndFunc

; Internal sub without error checking !
Func ARR_SORT_INDEXES(ByRef \$arr, \$i_start, \$i_end)
Local \$i_left, \$i_right, \$v_pivot, \$v_swap, \$i, \$j
Local Const \$i_ins_sort_1d = 20

If \$i_end <= \$i_start Then Return

; InsertionSort (faster for smaller segments)
If (\$i_end - \$i_start) <= \$i_ins_sort_1d Then
For \$i = (\$i_start + 1) To \$i_end
\$v_pivot = \$arr[\$i]
For \$j = (\$i - 1) To \$i_start Step -1
If \$v_pivot >= \$arr[\$j] Then ExitLoop
\$arr[\$j + 1] = \$arr[\$j]
Next
\$arr[\$j + 1] = \$v_pivot
Next
Return
EndIf

; QuickSort
\$i_left = \$i_start
\$i_right = \$i_end
\$v_pivot = \$arr[Int((\$i_start + \$i_end) / 2)]
Do
While \$arr[\$i_left] < \$v_pivot
\$i_left = \$i_left + 1
WEnd
While \$arr[\$i_right] > \$v_pivot
\$i_right = \$i_right - 1
WEnd

; Swap
If \$i_left <= \$i_right Then
\$v_swap = \$arr[\$i_left]
\$arr[\$i_left] = \$arr[\$i_right]
\$arr[\$i_right] = \$v_swap
\$i_left = \$i_left + 1
\$i_right = \$i_right - 1
EndIf
Until \$i_left > \$i_right

ARR_SORT_INDEXES(\$arr, \$i_start, \$i_right)
ARR_SORT_INDEXES(\$arr, \$i_left, \$i_end)
EndFunc```

************************************************************************************************************************************************

For completeness I also give the same functions (sorting & binary searching) for 1D arrays, in a example script.
Code for 1D arrays :

```AutoItSetOption("MustDeclareVars", 1)

MAIN()

Func MAIN()
Local \$b_isnum, \$i_searched_size, \$i_speed_size, \$b_stablesort

\$i_searched_size = \$i_searched_size
\$i_speed_size = \$i_speed_size

\$b_stablesort = True
\$b_stablesort = False

\$b_isnum = True
\$b_isnum = False

\$i_searched_size = 30
TEST_SORT_BINFIND(\$i_searched_size, \$b_isnum, \$b_stablesort)

; for 5000 items :
; 0.90s for numbers (1.08s with stable sort), 1.15s for strings (1.34s with stable sort), on my old computer
\$i_speed_size = 5000
TEST_SORT_SPEED(\$i_speed_size, \$b_isnum, \$b_stablesort)
EndFunc

Func TEST_SORT_BINFIND(\$i_searched_size, \$b_isnum, \$b_stablesort)
Local \$i_msg, \$v_searched, \$s_res, \$b_newarr, \$b_ressort, \$s_i, \$i
Local \$arr, \$arr_bak, \$arr_searching, \$arr_found, \$arr_acc

Local Const \$h_gui = GUICreate("ARRAY_1D SORT & BINARY FIND", 800, 700, Default, Default, BitOR(0x00040000, 0x00020000))
Local Const \$id_edit = GUICtrlCreateEdit("", 5, 5, 790, 645, BitOR(0x800, 0x00100000, 0x00200000))
GUICtrlSetResizing(Default, 102)
GUICtrlSetFont(Default, 9, 400, 0, "courier new")
Local Const \$id_button_newarr = GUICtrlCreateButton("&New Array (F5)", 5, 655, 120, 20, 0x1)
GUICtrlSetResizing(Default, 66 + 768)
Local Const \$id_button_resort = GUICtrlCreateButton("&Re-Sort Array (F6)", 670, 655, 120, 20)
GUICtrlSetResizing(Default, 68 + 768)
GUICtrlSetTip(Default, _
"Basic Quicksort is not 'stable' by itself," & @CR & _
"so identical (according to the criterion(s)) items" & @CR & _
"can be swapped after a re-sort action" & @CR & _
@CR & _
"But if \$b_stablesort is set to True" & @CR & _
"original order between identical items is preserved" & @CR & _
"(increases processing time by ~10-20%)")

Dim \$arr_acc[2][2] = [ _
["{F5}", \$id_button_newarr], _
["{F6}", \$id_button_resort] _
]
GUISetAccelerators(\$arr_acc, \$h_gui)
GUISetState(@SW_SHOW, \$h_gui)

; test code for sort & search
\$b_newarr = True
While True
If \$b_newarr Then
Dim \$arr[\$i_searched_size]
For \$i = 0 To UBound(\$arr) - 1
If \$b_isnum Then
\$arr[\$i] = Random(-4, 4, 1)
Else
\$arr[\$i] = MAKE_STRING("a", "c", 2)
EndIf
Next
\$arr_bak = \$arr
EndIf

If \$b_isnum Then
\$v_searched = 1
Else
\$v_searched = "ba"
EndIf

; sort/search criterion : [ascending, case sensitive, value searched], must be the same for sorting & searching
Dim \$arr_searching[3] = [True, False, \$v_searched]

\$b_ressort = ARRAY_1D_SORT(\$arr, 0, UBound(\$arr) - 1, \$arr_searching[0], \$arr_searching[1], \$b_stablesort)
\$arr_found = ARRAY_1D_BINARY_FINDALL(\$arr, 0, UBound(\$arr) - 1, \$arr_searching[0], \$arr_searching[1], \$arr_searching[2])

\$s_res = ""
For \$i = 0 To UBound(\$arr) - 1
\$s_i = \$i
If \$i < 10 Then \$s_i = "0" & \$i
\$s_res = \$s_res & \$s_i & "|"
Next
\$s_res = \$s_res & " -> sorted indexes" & @CRLF & @CRLF
For \$i = 0 To UBound(\$arr_bak) - 1
If StringLen(\$arr_bak[\$i]) < 2 Then \$s_res = \$s_res & " "
\$s_res = \$s_res & \$arr_bak[\$i] & "|"
Next
\$s_res = \$s_res & " -> original array" & @CRLF & @CRLF
For \$i = 0 To UBound(\$arr) - 1
If StringLen(\$arr[\$i]) < 2 Then \$s_res = \$s_res & " "
\$s_res = \$s_res & \$arr[\$i] & "|"
Next
\$s_res = \$s_res & " -> array sorted" & @CRLF
For \$i = 0 To UBound(\$arr) - 1
For \$j = 1 To UBound(\$arr_found) - 1
If \$arr_found[\$j] = \$i Then
\$s_res = \$s_res & " +|"
ExitLoop
EndIf
Next
If \$j = UBound(\$arr_found) Then \$s_res = \$s_res & "  |"
Next
\$s_res = \$s_res & " -> found(+)" & @CRLF & @CRLF

\$s_res = \$s_res & "Array sorted : " & \$b_ressort
If \$b_stablesort Then
\$s_res = \$s_res & ", Stable sort : True" & @CRLF & @CRLF
Else
\$s_res = \$s_res & ", Stable sort : False" & @CRLF & @CRLF
EndIf

\$s_res = \$s_res & "Sorting & searching array criterion :" & @CRLF
\$s_res = \$s_res & _
"Ascending:" & \$arr_searching[0] & " | " & _
"Casesens:" & \$arr_searching[1] & " | " & _
"Searching value:" & \$arr_searching[2] & @CRLF & @CRLF

\$s_res = \$s_res & \$arr_found[0] & " searched indexes found : "
For \$i = 1 To UBound(\$arr_found) - 1
\$s_res = \$s_res & \$arr_found[\$i]
If \$i < UBound(\$arr_found) - 1 Then \$s_res = \$s_res & " | "
Next
\$s_res = \$s_res & @CRLF

GUICtrlSetData(\$id_edit, \$s_res)
While True
\$i_msg = GUIGetMsg()
If \$i_msg = -3 Then
GUISetState(@SW_HIDE, \$h_gui)
Return
EndIf
If \$i_msg = \$id_button_newarr Then
\$b_newarr = True
ExitLoop
EndIf
If \$i_msg = \$id_button_resort Then
\$b_newarr = False
ExitLoop
EndIf
WEnd
WEnd
EndFunc

Func TEST_SORT_SPEED(\$i_speed_size, \$b_isnum, \$b_stablesort)
Local \$d_timer, \$i_ms_timerdiff, \$b_ressort, \$s_text
Local \$arr, \$arr_sorting

Dim \$arr[\$i_speed_size]

Do
ToolTip(@CR & " Speed test... " & @CR)
For \$i = 0 To UBound(\$arr) - 1
If \$b_isnum Then
\$arr[\$i] = Random(0, 0x7FFFFFFF, 1)
Else
\$arr[\$i] = Hex(Random(0, 0x7FFFFFFF, 1))
EndIf
Next

; change this array to change the sort : ascending, casesens
Dim \$arr_sorting[2] = [True, False]

\$d_timer = TimerInit()
\$b_ressort = ARRAY_1D_SORT(\$arr, 0, UBound(\$arr) - 1, \$arr_sorting[0], \$arr_sorting[1], \$b_stablesort)
\$i_ms_timerdiff = TimerDiff(\$d_timer)

\$s_text = (\$i_ms_timerdiff / 1000) & " s for " & \$i_speed_size & " sorted lines" & @CRLF
If \$b_isnum Then
\$s_text = \$s_text & "with numbers"
Else
\$s_text = \$s_text & "with strings"
EndIf
\$s_text = \$s_text & ", Stable sort : " & \$b_stablesort & @CRLF & @CRLF

ToolTip("")
Until MsgBox(5 + 64 + 4096, "Sorted : " & \$b_ressort, \$s_text) <> 4
EndFunc

Func MAKE_STRING(\$s_char_1, \$s_char_2, \$i_len)
Local \$s_res, \$i_char_1, \$i_char_2

\$i_char_1 = Asc(StringLower(\$s_char_1))
\$i_char_2 = Asc(StringLower(\$s_char_2))

\$s_res = ""
For \$i = 1 To \$i_len
If Random(0, 1, 1) = 0 Then
\$s_res = \$s_res & StringUpper(Chr(Random(\$i_char_1, \$i_char_2, 1)))
Else
\$s_res = \$s_res & Chr(Random(\$i_char_1, \$i_char_2, 1))
EndIf
Next
Return \$s_res
EndFunc

; **************************************************************************************************
; End of example script, beginning of reusable functions *******************************************
; **************************************************************************************************

; Arrays 1D ****************************************************************************************
; function always returns a 1D array, on success containing the indexes of the found item(s)
; if n items found : [n, index_1, ... index_n] (n+1 slots array, the first slot gives the number of items found)
; if no item found (possibly \$i_end < \$i_start) : [0] (one slot array), on input error : [-1] (one slot array)
;
;   array MUST BE SORTED between \$i_start and \$i_end BEFORE binary searching this range
;   (in the direction defined by \$b_ascending, and with the case defined by \$b_casesensitive)
;   or function may return less matching items (possibly none) than there are !
;
;   the var TYPE (number or string) of \$v_searching sets the type of comparison (as numbers or strings) done in the array
Func ARRAY_1D_BINARY_FINDALL(ByRef \$arr, \$i_start, \$i_end, \$b_ascending, \$b_casesensitive, \$v_searching)
Local \$s_indexes_found, \$i_casecomp, \$b_isnum, \$i_respos, \$i_mid, \$i
Local \$arr_err, \$arr_none
Local Const \$i_stringcomp_casesens      = 1
Local Const \$i_stringcomp_not_casesens  = 2

Dim \$arr_err[1] = [-1]
Dim \$arr_none[1] = [0]

If Not(IsArray(\$arr)) Then Return \$arr_err
If UBound(\$arr, 0) <> 1 Then Return \$arr_err

If \$i_start < 0 Then \$i_start = 0
If \$i_end > (UBound(\$arr) - 1) Then \$i_end = UBound(\$arr) - 1
If \$i_end < \$i_start Then Return \$arr_none

If \$b_casesensitive Then
\$i_casecomp = \$i_stringcomp_casesens
Else
\$i_casecomp = \$i_stringcomp_not_casesens
EndIf
\$b_isnum = IsNumber(\$v_searching)

; off-limits test
\$i_respos = ARRAY_1D_BINARY_FINDALL_POS(\$v_searching, \$b_ascending, \$i_casecomp, \$b_isnum, \$arr[\$i_start])
If \$i_respos > 0 Then Return \$arr_none
\$i_respos = ARRAY_1D_BINARY_FINDALL_POS(\$v_searching, \$b_ascending, \$i_casecomp, \$b_isnum, \$arr[\$i_end])
If \$i_respos < 0 Then Return \$arr_none

Do
; mid test
\$i_mid = Int((\$i_start + \$i_end) / 2)
\$i_respos = ARRAY_1D_BINARY_FINDALL_POS(\$v_searching, \$b_ascending, \$i_casecomp, \$b_isnum, \$arr[\$i_mid])

; 1 item found, find others
If \$i_respos = 0 Then
\$s_indexes_found = \$i_mid
For \$i = (\$i_mid - 1) To \$i_start Step -1
If \$b_isnum Then
If \$arr[\$i] <> \$v_searching Then ExitLoop
Else
If StringCompare(\$arr[\$i], \$v_searching, \$i_casecomp) <> 0 Then ExitLoop
EndIf
\$s_indexes_found = \$i & "," & \$s_indexes_found
Next
For \$i = (\$i_mid + 1) To \$i_end
If \$b_isnum Then
If \$arr[\$i] <> \$v_searching Then ExitLoop
Else
If StringCompare(\$arr[\$i], \$v_searching, \$i_casecomp) <> 0 Then ExitLoop
EndIf
\$s_indexes_found = \$s_indexes_found & "," & \$i
Next
Return StringSplit(\$s_indexes_found, ",")
EndIf

; change borders
If \$i_respos > 0 Then
\$i_end = \$i_mid - 1
Else
\$i_start = \$i_mid + 1
EndIf
Until \$i_start > \$i_end

Return \$arr_none
EndFunc

; Internal sub without error checking !
; function returns 0, 1, or -1 : 1 if \$v_tested is after \$v_searching, -1 if before, 0 if equal
Func ARRAY_1D_BINARY_FINDALL_POS(\$v_searching, \$b_ascending, \$i_casecomp, \$b_isnum, \$v_tested)
Local \$i_rescomp

If \$b_isnum Then
If ((\$b_ascending And \$v_tested > \$v_searching) Or (Not(\$b_ascending) And \$v_tested < \$v_searching)) Then Return 1
If ((\$b_ascending And \$v_tested < \$v_searching) Or (Not(\$b_ascending) And \$v_tested > \$v_searching)) Then Return -1
Else
\$i_rescomp = StringCompare(\$v_tested, \$v_searching, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp > 0) Or (Not(\$b_ascending) And \$i_rescomp < 0)) Then Return 1
If ((\$b_ascending And \$i_rescomp < 0) Or (Not(\$b_ascending) And \$i_rescomp > 0)) Then Return -1
EndIf
Return 0
EndFunc

; function returns True (possibly \$i_end <= \$i_start), or False on input error
; \$b_stablesort : if True, with some time cost, preserve order of identical (according to the sorting criterion(s)) items
Func ARRAY_1D_SORT(ByRef \$arr, \$i_start, \$i_end, \$b_ascending, \$b_casesensitive, \$b_stablesort)
Local \$v_first, \$v_tested, \$i_casecomp, \$i, \$j
Local \$arr_tmp, \$arr_storedin
Local Const \$i_stringcomp_casesens      = 1
Local Const \$i_stringcomp_not_casesens  = 2

If Not(IsArray(\$arr)) Then Return False
If UBound(\$arr, 0) <> 1 Then Return False

If \$i_start < 0 Then \$i_start = 0
If \$i_end > (UBound(\$arr) - 1) Then \$i_end = UBound(\$arr) - 1
If \$i_end <= \$i_start Then Return True

If \$b_casesensitive Then
\$i_casecomp = \$i_stringcomp_casesens
Else
\$i_casecomp = \$i_stringcomp_not_casesens
EndIf

; init virtual sort : \$arr_storedin[\$i] gives the index in \$arr where the item \$i is currently stored
Dim \$arr_storedin[UBound(\$arr)]
For \$i = \$i_start To \$i_end
\$arr_storedin[\$i] = \$i
Next

ARRAY_1D_SORT_DOSORT(\$arr, \$arr_storedin, \$i_start, \$i_end, \$b_ascending, \$i_casecomp)

; stable sort option : re-order ascendingly \$arr_storedin indexes pointing to
; identical (according to the sorting criterion) items
If \$b_stablesort Then
\$i = \$i_start
While \$i < \$i_end
\$j = \$i + 1
While \$j <= \$i_end
\$v_first = \$arr[\$arr_storedin[\$i]]
\$v_tested = \$arr[\$arr_storedin[\$j]]

If (IsNumber(\$v_first) And IsNumber(\$v_tested)) Then
If \$v_first <> \$v_tested Then ExitLoop
Else
If StringCompare(\$v_first, \$v_tested, \$i_casecomp) <> 0 Then ExitLoop
EndIf
\$j = \$j + 1
WEnd
ARR_SORT_INDEXES(\$arr_storedin, \$i, \$j - 1)
\$i = \$j
WEnd
EndIf

; apply virtual sort
\$arr_tmp = \$arr
For \$i = \$i_start To \$i_end
\$arr[\$i] = \$arr_tmp[\$arr_storedin[\$i]]
Next

Return True
EndFunc

; Internal sub without error checking !
; virtual sorting is done : items in \$arr are not swapped, instead indexes are swapped in \$arr_storedin
Func ARRAY_1D_SORT_DOSORT(ByRef \$arr, ByRef \$arr_storedin, \$i_start, \$i_end, \$b_ascending, \$i_casecomp)
Local \$i_left, \$i_right, \$b_isnum, \$i_rescomp, \$v_pivot, \$v_tested, \$i_pivot, \$i_swap, \$i, \$j
Local Const \$i_ins_sort_1d = 20

If \$i_end <= \$i_start Then Return

; InsertionSort (faster for smaller segments)
If (\$i_end - \$i_start) <= \$i_ins_sort_1d Then
For \$i = (\$i_start + 1) To \$i_end
\$i_pivot = \$arr_storedin[\$i]
\$v_pivot = \$arr[\$i_pivot]
\$b_isnum = IsNumber(\$v_pivot)

For \$j = (\$i - 1) To \$i_start Step -1
\$v_tested = \$arr[\$arr_storedin[\$j]]
If (\$b_isnum And IsNumber(\$v_tested)) Then
If ((\$b_ascending And \$v_pivot >= \$v_tested) Or (Not(\$b_ascending) And \$v_pivot <= \$v_tested)) Then ExitLoop
Else
\$i_rescomp = StringCompare(\$v_pivot, \$v_tested, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp >= 0) Or (Not(\$b_ascending) And \$i_rescomp <= 0)) Then ExitLoop
EndIf
\$arr_storedin[\$j + 1] = \$arr_storedin[\$j]
Next
\$arr_storedin[\$j + 1] = \$i_pivot
Next
Return
EndIf

; QuickSort
\$i_left = \$i_start
\$i_right = \$i_end
\$v_pivot = \$arr[\$arr_storedin[Int((\$i_start + \$i_end) / 2)]]
\$b_isnum = IsNumber(\$v_pivot)
Do
While True
\$v_tested = \$arr[\$arr_storedin[\$i_left]]

If (\$b_isnum And IsNumber(\$v_tested)) Then
If ((\$b_ascending And \$v_tested >= \$v_pivot) Or (Not(\$b_ascending) And \$v_tested <= \$v_pivot)) Then ExitLoop
\$i_left = \$i_left + 1
Else
\$i_rescomp = StringCompare(\$v_tested, \$v_pivot, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp >= 0) Or (Not(\$b_ascending) And \$i_rescomp <= 0)) Then ExitLoop
\$i_left = \$i_left + 1
EndIf
WEnd
While True
\$v_tested = \$arr[\$arr_storedin[\$i_right]]

If (\$b_isnum And IsNumber(\$v_tested)) Then
If ((\$b_ascending And \$v_tested <= \$v_pivot) Or (Not(\$b_ascending) And \$v_tested >= \$v_pivot)) Then ExitLoop
\$i_right = \$i_right - 1
Else
\$i_rescomp = StringCompare(\$v_tested, \$v_pivot, \$i_casecomp)
If ((\$b_ascending And \$i_rescomp <= 0) Or (Not(\$b_ascending) And \$i_rescomp >= 0)) Then ExitLoop
\$i_right = \$i_right - 1
EndIf
WEnd

; Swap
If \$i_left <= \$i_right Then
\$i_swap = \$arr_storedin[\$i_left]
\$arr_storedin[\$i_left] = \$arr_storedin[\$i_right]
\$arr_storedin[\$i_right] = \$i_swap
\$i_left = \$i_left + 1
\$i_right = \$i_right - 1
EndIf
Until \$i_left > \$i_right

ARRAY_1D_SORT_DOSORT(\$arr, \$arr_storedin, \$i_start, \$i_right, \$b_ascending, \$i_casecomp)
ARRAY_1D_SORT_DOSORT(\$arr, \$arr_storedin, \$i_left, \$i_end, \$b_ascending, \$i_casecomp)
EndFunc

; Internal sub without error checking !
Func ARR_SORT_INDEXES(ByRef \$arr, \$i_start, \$i_end)
Local \$i_left, \$i_right, \$v_pivot, \$v_swap, \$i, \$j
Local Const \$i_ins_sort_1d = 20

If \$i_end <= \$i_start Then Return

; InsertionSort (faster for smaller segments)
If (\$i_end - \$i_start) <= \$i_ins_sort_1d Then
For \$i = (\$i_start + 1) To \$i_end
\$v_pivot = \$arr[\$i]
For \$j = (\$i - 1) To \$i_start Step -1
If \$v_pivot >= \$arr[\$j] Then ExitLoop
\$arr[\$j + 1] = \$arr[\$j]
Next
\$arr[\$j + 1] = \$v_pivot
Next
Return
EndIf

; QuickSort
\$i_left = \$i_start
\$i_right = \$i_end
\$v_pivot = \$arr[Int((\$i_start + \$i_end) / 2)]
Do
While \$arr[\$i_left] < \$v_pivot
\$i_left = \$i_left + 1
WEnd
While \$arr[\$i_right] > \$v_pivot
\$i_right = \$i_right - 1
WEnd

; Swap
If \$i_left <= \$i_right Then
\$v_swap = \$arr[\$i_left]
\$arr[\$i_left] = \$arr[\$i_right]
\$arr[\$i_right] = \$v_swap
\$i_left = \$i_left + 1
\$i_right = \$i_right - 1
EndIf
Until \$i_left > \$i_right

ARR_SORT_INDEXES(\$arr, \$i_start, \$i_right)
ARR_SORT_INDEXES(\$arr, \$i_left, \$i_end)
EndFunc```

************************************************************************************************************************************************

This 2D sorting on multiple subitems may have already been done, however it was enough fun to do it by myself.
(I needed it to perform a multi-sort inside a listview)

I would be glad if someone was to test it (for bugs, performance improvements, etc...)
This code is free to use, modify, and if someone is willing to make it compliant with UDFs rules he can include any part of it in its own UDF.

Edited by marc0v

## Create an account

Register a new account

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...