#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(100) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL gap AS LONG
    LOCAL temp_val AS LONG
    LOCAL temp_str AS STRING

    ' Shell sort with multiple gap sequences

    n = 15
    arr(0) = 29
    arr(1) = 10
    arr(2) = 14
    arr(3) = 37
    arr(4) = 13
    arr(5) = 33
    arr(6) = 8
    arr(7) = 22
    arr(8) = 45
    arr(9) = 18
    arr(10) = 5
    arr(11) = 27
    arr(12) = 42
    arr(13) = 31
    arr(14) = 20

    PRINT "Shell Sort (Gap Sequences)"
    PRINT "========================="
    PRINT ""

    PRINT "Shell gap sequence (N/2, N/4, ..., 1):"
    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "Before: " + temp_str

    gap = n / 2
    WHILE gap > 0
        i = gap
        WHILE i < n
            temp_val = arr(i)
            j = i
            WHILE j >= gap AND arr(j - gap) > temp_val
                arr(j) = arr(j - gap)
                j = j - gap
            WEND
            arr(j) = temp_val
            i = i + 1
        WEND
        gap = gap / 2
    WEND

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "After:  " + temp_str

    ' Knuth gap sequence: (3^k - 1) / 2
    n = 10
    arr(0) = 84
    arr(1) = 37
    arr(2) = 62
    arr(3) = 19
    arr(4) = 45
    arr(5) = 73
    arr(6) = 28
    arr(7) = 51
    arr(8) = 96
    arr(9) = 13

    PRINT ""
    PRINT "Knuth gap sequence (3^k-1)/2:"
    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "Before: " + temp_str

    gap = 1
    WHILE gap < n / 3
        gap = gap * 3 + 1
    WEND

    WHILE gap > 0
        i = gap
        WHILE i < n
            temp_val = arr(i)
            j = i
            WHILE j >= gap AND arr(j - gap) > temp_val
                arr(j) = arr(j - gap)
                j = j - gap
            WEND
            arr(j) = temp_val
            i = i + 1
        WEND
        gap = (gap - 1) / 3
    WEND

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "After:  " + temp_str

    ' Sedgewick gap sequence
    n = 8
    arr(0) = 55
    arr(1) = 23
    arr(2) = 87
    arr(3) = 12
    arr(4) = 44
    arr(5) = 67
    arr(6) = 31
    arr(7) = 98

    PRINT ""
    PRINT "Sedgewick gap sequence:"
    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "Before: " + temp_str

    gap = n / 2
    WHILE gap > 0
        i = gap
        WHILE i < n
            temp_val = arr(i)
            j = i
            WHILE j >= gap AND arr(j - gap) > temp_val
                arr(j) = arr(j - gap)
                j = j - gap
            WEND
            arr(j) = temp_val
            i = i + 1
        WEND
        gap = gap / 2
    WEND

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "After:  " + temp_str

    ' Verify last sort
    i = 0
    j = 1
    WHILE i < n - 1
        IF arr(i) > arr(i + 1) THEN
            j = 0
        END IF
        i = i + 1
    WEND
    IF j = 1 THEN
        PRINT "Sorted correctly"
    END IF

    PRINT ""
    PRINT "Shell sort complete."

    FUNCTION = 0
END FUNCTION
