Tech Tip: Method to correctly insert a value in a sorted array
PRODUCT: 4D | VERSION: 14 R4 | PLATFORM: Mac & Win
Published On: March 16, 2015
Below is a method to correctly place a value in a sorted array maintianing the order.
// Method: InsertInSortedArray // Description: Will insert a value in the // correct position of a sorted array // Parameters // $1 - Pointer to the Sorted Array // $2 - Pointer to the value that will be added to the array // $3 - String that let the method know which direction the array is sorted in // "<" - Decending order // ">" - Ascending order C_POINTER($1;$arrPtr) C_POINTER($2;$valuePtr) C_TEXT($3;$opperator_t) C_LONGINT($pos_l) If (Count parameters>=3) $arrPtr:=$1 $valuePtr:=$2 $opperator_t:=$3 Case of : ($opperator_t="<") Find in sorted array($arrPtr->;$valuePtr->;<;$pos_l) INSERT IN ARRAY($arrPtr->;$pos_l) $arrPtr->{$pos_l}:=$valuePtr-> : ($opperator_t=">") Find in sorted array($arrPtr->;$valuePtr->;>;$pos_l) INSERT IN ARRAY($arrPtr->;$pos_l) $arrPtr->{$pos_l}:=$valuePtr-> End case End if |
This method takes advantage of the new Find in sorted array command that will try to find the first, and last if wanted, positions of a value in the array or the position where the value would be. The value is passed as a parameter to handle different types, such as integers or texts. The new Find in sorted array uses a binary search algorithm which is efficient for large arrays and will be faster than appending a value to an array and then sorting it after.
Below is an example of using the method:
ARRAY TEXT($arrT;0) APPEND TO ARRAY($arrT;"a") APPEND TO ARRAY($arrT;"a") APPEND TO ARRAY($arrT;"b") APPEND TO ARRAY($arrT;"d") APPEND TO ARRAY($arrT;"d") APPEND TO ARRAY($arrT;"e") C_TEXT($valT) $valT:="c" ARRAY LONGINT($arrL;0) APPEND TO ARRAY($arrL;5) APPEND TO ARRAY($arrL;5) APPEND TO ARRAY($arrL;4) APPEND TO ARRAY($arrL;3) APPEND TO ARRAY($arrL;2) APPEND TO ARRAY($arrL;2) APPEND TO ARRAY($arrL;1) C_LONGINT($valL) $valL:=3 InsertInSortedArray (->$arrL;->$valL;"<") InsertInSortedArray(->$arrT;->$valT;">") |
The results of the arrays are:
$arrL - {5, 5, 4, 3, 3, 2, 2, 1}
$arrT - {"a", "a", "b", "c", "d", "d", "e"}