marc0v Posted October 21, 2014 Share Posted October 21, 2014 (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 : expandcollapse popupAutoItSetOption("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 : expandcollapse popupAutoItSetOption("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 October 21, 2014 by marc0v Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now