Sign in to follow this  
Followers 0
marc0v

Array 2D Sort/Binary Find on multiple subitems

1 post in this topic

#1 ·  Posted (edited)

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

Share this post


Link to post
Share on other sites



Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0