' Insertion Sort — builds final sorted array one element at a time
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(1000) AS LONG
    LOCAL tmpArr(1000) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL key AS LONG
    LOCAL compCount AS LONG
    LOCAL shiftCount AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    LOCAL seed AS LONG
    LOCAL foundPos AS LONG
    n = 50
    PRINT "============================================"
    PRINT "         INSERTION SORT DEMONSTRATION"
    PRINT "============================================"
    PRINT ""
    PRINT "Original array:"
    PRINT ""
    FOR i = 0 TO n - 1
        arr(i) = ((i * 23 + 11) MOD 97) + 1
    NEXT i
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    compCount = 0
    shiftCount = 0
    FOR i = 1 TO n - 1
        key = arr(i)
        j = i - 1
        DO WHILE j >= 0 AND arr(j) > key
            compCount = compCount + 1
            arr(j + 1) = arr(j)
            shiftCount = shiftCount + 1
            j = j - 1
        LOOP
        IF j >= 0 THEN
            compCount = compCount + 1
        END IF
        arr(j + 1) = key
    NEXT i
    PRINT "Sorted array:"
    PRINT ""
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    PRINT "Comparisons: " + STR$(compCount) + "  Shifts: " + STR$(shiftCount)
    PRINT ""
    PRINT "============================================"
    PRINT "       BINARY INSERTION SORT"
    PRINT "============================================"
    PRINT ""
    n = 15
    FOR i = 0 TO n - 1
        arr(i) = ((i * 29 + 5) MOD 53) + 10
    NEXT i
    PRINT "Before:"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    FOR i = 1 TO n - 1
        key = arr(i)
        foundPos = 0
        compCount = 0
        DO WHILE compCount < i AND arr(compCount) <= key
            compCount = compCount + 1
        LOOP
        foundPos = compCount
        FOR j = i TO foundPos + 1 STEP -1
            arr(j) = arr(j - 1)
        NEXT j
        arr(foundPos) = key
    NEXT i
    PRINT "After:"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    PRINT ""
    PRINT "============================================"
    PRINT "     PARTIALLY SORTED (almost sorted)"
    PRINT "============================================"
    PRINT ""
    n = 20
    FOR i = 0 TO n - 1
        arr(i) = i + 1
    NEXT i
    arr(5) = 19
    arr(10) = 3
    arr(15) = 17
    PRINT "Before (nearly sorted):"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    compCount = 0
    shiftCount = 0
    FOR i = 1 TO n - 1
        key = arr(i)
        j = i - 1
        DO WHILE j >= 0 AND arr(j) > key
            compCount = compCount + 1
            arr(j + 1) = arr(j)
            shiftCount = shiftCount + 1
            j = j - 1
        LOOP
        IF j >= 0 THEN
            compCount = compCount + 1
        END IF
        arr(j + 1) = key
    NEXT i
    PRINT "After:"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    PRINT ""
    PRINT "Comparisons: " + STR$(compCount) + "  Shifts: " + STR$(shiftCount)
    PRINT ""
    PRINT "============================================"
    PRINT "     DUPLICATE ELEMENTS IN INSERTION SORT"
    print "============================================"
    PRINT ""
    n = 15
    FOR i = 0 TO n - 1
        arr(i) = (i * 3) MOD 7 + 1
    NEXT i
    PRINT "Before (with duplicates):"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    FOR i = 1 TO n - 1
        key = arr(i)
        j = i - 1
        DO WHILE j >= 0 AND arr(j) > key
            arr(j + 1) = arr(j)
            j = j - 1
        LOOP
        arr(j + 1) = key
    NEXT i
    PRINT "After:"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    PRINT ""
    PRINT "Verification:"
    i = 0
    DO WHILE i < n - 1
        IF arr(i) > arr(i + 1) THEN
            PRINT "FAIL at position " + STR$(i)
        END IF
        i = i + 1
    LOOP
    PRINT "Insertion sort complete"
    FUNCTION = 0
END FUNCTION
