KNOWLEDGE BASE
Log In    |    Knowledge Base    |    4D Home
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"}