'+==============================================+
'|                I-INSERT.BAS                  |
'|             By Lawrence Stone                |
'|                  02/12/92                    |
'|                                              |
'|  Purpose:  Demonstrate insert sort routine   |
'|            on integer arrays using B$ASSN.   |
'+----------------------------------------------+
DEFINT A-Z

DECLARE SUB QuickInsert (LastElement%, Value%, Arry%())

DECLARE SUB QBMemCopy ALIAS "B$ASSN" (SEG FromAddress, _
BYVAL BytesFrom%, SEG ToAddress, BYVAL BytesTo%)

'---- Array we will be inserting into
DIM SortArray%(1 TO 150)

'---- Used by QuickInsert for temporary storage
DIM SHARED TempSortArray%(1 TO 150)

CLS

PRINT "Unsorted Values..."

FOR LastElement% = 1 TO 150
    READ Value
    PRINT Value;          ' Display the unsorted value
   
    '---- Insert the value into its appropriate position.
    QuickInsert LastElement%, Value, SortArray%()
NEXT

PRINT : PRINT
PRINT "Sorted Values..."

'---- Display our sorted values
FOR N = 1 TO 150
    PRINT SortArray(N);
NEXT

END

'---- Random numbers between 1 and 150
DATA 59,109,54,111,33,90,144,86,11,30,127,3,94,19,91,60,108,58,73,9,21
DATA 23,40,101,100,107,66,128,43,97,110,42,143,25,65,74,125,46,129,78
DATA 112,104,99,8,31,24,145,51,2,118,16,150,95,55,102,64,98,71,7,77,137
DATA 113,119,141,29,4,72,80,105,18,126,49,70,115,17,120,38,122,69,50,56
DATA 135,147,83,62,61,27,136,34,37,6,57,121,39,93,15,89,82,139,79,132
DATA 32,35,138,142,92,148,140,96,88,84,22,45,67,85,130,133,116,131,1,106
DATA 87,47,146,13,12,52,134,114,26,124,48,103,75,28,117,36,44,68,10,123
DATA 14,53,76,41,20,63,5,81,149

SUB QuickInsert (LastElement%, Value%, Arry%()) STATIC
   
    begin% = LBOUND(Arry%)
    Low% = begin%
    ending% = LastElement%
                          
    '---- Binary search toward area of insertion point (fast).
    DO WHILE begin% <= ending%

        '---- Set middle midway between begin and ending
        middle% = (begin% + ending%) \ 2
       
        IF middle% > Low% AND middle% < LastElement% THEN
            '---- Bail out if we're at the spot
            IF Value% > Arry%(middle% - 1) AND Value% < Arry%(middle%) _
            THEN EXIT DO
        END IF

        IF Value% = Arry%(middle%) THEN     'We found a match so bail out
            EXIT DO
        ELSEIF Value% > Arry%(middle%) THEN 'Look higher up in the array
            begin% = middle% + 1
        ELSE                                'Look lower down the array
            ending% = middle% - 1
        END IF
    LOOP
   
    '**************************************************************
    '---- This REMmed loop would then adjust one element at a time.
    '     This is how it must be done from within the QB or QBX
    '     environment.

    'FOR N% = LastElement% - 1 TO middle% STEP -1
        'Arry%(N% + 1) = Arry%(N%)
    'NEXT
    'Arry%(middle%) = Value%
    'EXIT SUB
    '**************************************************************
   

    '---- Use this routine in compiled QB (or PDS).  It is EXTREMELY
    '     quick.  It works by copying all of the array's data from
    '     the insertion point through the last element to a temporary
    '     holding array in one quick move.  Then copies from the temp
    '     holding array back to our original array at a location one
    '     element past the insertion point.  Again in one quick move.
    '     It will not work from within the QB or QBX environment so
    '     use the REMmed code above within the environment and the
    '     code below for compiled programs.
    
    '---- Determine the number of bytes to move (64K max)
    MoveBytes% = (LastElement% - middle%) * LEN(Arry%(Low%))
    
    IF MoveBytes% THEN
        '---- Get the lower bound of TempSortArray
        Low% = LBOUND(TempSortArray%)
       
        '---- Copy from our Arry(middle) to TempSortArray
        CALL QBMemCopy(Arry%(middle%), MoveBytes%, _
        TempSortArray%(Low%), MoveBytes%)
       
        '---- Now copy from TempSortArray to Arry(middle + 1)
        CALL QBMemCopy(TempSortArray%(Low%), MoveBytes%, _
        Arry%(middle% + 1), MoveBytes%)
    END IF
   
    '---- Now that data is moved, set the new value into the array at
    '     it's appropriate insertion point
    Arry%(middle%) = Value%

END SUB