;------------------------------------------------------------------------------------------------------------------------------------------
#DefineFunction udfArrayShellSortK (arrArray)
If !ArrInfo (arrArray, -1) Then Return ArrDimension (0) ; Invalid input array, return empty valid dim-0 array.
If ArrInfo (arrArray, 0) != 1 Then Return ArrDimension (0) ; Only dim-1 array allowed, return empty valid dim-0 array.
intElements = ArrInfo (arrArray, 1)
If intElements == 0 Then Return ArrDimension (0) ; Input array has no elements, return empty valid dim-0 array.
If intElements == 1 Then Return arrArray ; Input array has only one element, return the input array.

; Establish increment sequence (recommended by Knuth, due to Sedgewick).
arrStep = ArrDimension (28) ; 28 elements in arrStep fit for (2**31)-1 elements in arrArray.
intP1 = 1
intP2 = 1
intP3 = 1
intS = -1
While @TRUE
   intS = intS + 1
   If intS mod 2
      arrStep [intS] = 1 + (8 * intP1) - (6 * intP2)
   Else
      arrStep [intS] = 1 + (9 * intP1) - (9 * intP3)
      intP2 = 2 * intP2
      intP3 = 2 * intP3
   EndIf
   intP1 = 2 * intP1
   If 3 * arrStep [intS] >= intElements Then Break
EndWhile
If intS > 0 Then intS = intS - 1

; ShellSort
intArrHigh = intElements - 1
intArrLow = 0
While intS >= 0
   intStep = arrStep [intS]
   intILow = intArrLow + intStep
   For intI = intILow To intArrHigh
      anyValue = arrArray [intI]
      intKLow = intI - intStep
      For intK = intKLow To intArrLow By -intStep
         If !(arrArray [intK] > anyValue) Then Break
         arrArray [intK + intStep] = arrArray [intK]
      Next
      arrArray [intK + intStep] = anyValue
   Next
   intS = intS - 1
EndWhile
Drop (arrStep)
Return arrArray
;..........................................................................................................................................
; ShellSort algorithm with Knuth's increment sequence adapted from the Visual Basic example in
; 'Sorting and Searching Algorithms, Thomas Niemann, ePaperPress, sortsearch.pdf, 12.05.2002 13:50:30'.
;..........................................................................................................................................
; ShellSort, developed by Donald L. Shell, is a non-stable in-place sort.
; ShellSort improves on the efficiency of insertion sort by quickly shifting values to their destination.
; For further reading, consult:
; Knuth, Donald. E.  [1998]. The Art of Computer Programming, Volume 3,
; Sorting and Searching. Addison-Wesley, Reading, Massachusetts.
;..........................................................................................................................................
#EndFunction
;------------------------------------------------------------------------------------------------------------------------------------------


;----------------------------------------------------------------------------------------------------------------------
#DefineFunction udfArrayItemize (arrArray, strDelimiter)
If !ArrInfo (arrArray, -1) Then Return "" ; No array.
If !ArrInfo (arrArray, 6) Then Return "" ; No elements.
If ArrInfo (arrArray, 0) > 1 Then Return "" ; Too much dimensions.
strItemList = ""
intHigh = Max (ArrInfo (arrArray, 1) - 1, 0)
intLow = 0
For intElem = intLow To intHigh
   If !!VarType (arrArray [intElem])
      strItemList = ItemInsert (arrArray [intElem], -1, strItemList, strDelimiter)
   Else
      strItemList = ItemInsert ("", -1, strItemList, strDelimiter)
   EndIf
Next
Return strItemList
;----------------------------------------------------------------------------------------------------------------------
; This UDF "udfArrayItemize" converts a given dim-1 array into an itemlist
; with each item separated by delimiter character.
;
; Example: strMyItemList = udfArrayItemize (arrMyArray, @TAB)
; Creates an itemList from array.
;
; Note:
; This UDF supports only dim-1 array.
; An array element which is not initialized has a Vartype=0 (undefined).
; Therefore an empty item will be appended to target itemlist.
;
; Detlev Dalitz.20020718.20090508.
;----------------------------------------------------------------------------------------------------------------------
#EndFunction
;----------------------------------------------------------------------------------------------------------------------


; Test.

strMsgTitle = "Demo: udfArrayShellSortK (arrArray)"
strMsgText = ""

strDelimiter = ","
strItemList = "22,q,w,e,r,t,T,999,a,s,d,f,1,/z,B5,-196" ; 16 Items.

arrA = Arrayize (strItemList, strDelimiter)
arrB = Arrayize (strItemList, strDelimiter)

arrB = udfArrayShellSortK (arrB)

strMsgText = strMsgText : "Array A: " : @LF : udfArrayItemize (arrA, strDelimiter) : @LF : @LF ; "22,q,w,e,r,t,T,999,a,s,d,f,1,/z,B5,-196"
strMsgText = strMsgText : "Array B sorted: " : @LF : udfArrayItemize (arrB, strDelimiter) : @LF : @LF ; "/z,-196,1,22,999,a,B5,d,e,f,q,r,s,t,T,w"

Message (strMsgTitle, strMsgText)

Exit