' Bubble Sort — standard O(n^2) sorting algorithm
#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 temp AS LONG
    LOCAL swapped AS LONG
    LOCAL passCount AS LONG
    LOCAL compCount AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    n = 50
    PRINT "============================================"
    PRINT "           BUBBLE SORT DEMONSTRATION"
    PRINT "============================================"
    PRINT ""
    PRINT "Original array (randomized):"
    PRINT ""
    FOR i = 0 TO n - 1
        arr(i) = ((i * 17 + 31) 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 ""
    passCount = 0
    compCount = 0
    FOR i = 0 TO n - 2
        swapped = 0
        FOR j = 0 TO n - 2 - i
            compCount = compCount + 1
            IF arr(j) > arr(j + 1) THEN
                temp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = temp
                swapped = 1
            END IF
        NEXT j
        passCount = passCount + 1
        IF swapped = 0 THEN
            EXIT FOR
        END IF
    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 "Passes: " + STR$(passCount) + "  Comparisons: " + STR$(compCount)
    PRINT ""
    PRINT "============================================"
    PRINT "       BUBBLE SORT WITH EARLY EXIT"
    PRINT "============================================"
    PRINT ""
    n = 20
    FOR i = 0 TO n - 1
        arr(i) = (i * 7 + 11) MOD 50
    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 = 0 TO n - 2
        swapped = 0
        FOR j = 0 TO n - 2 - i
            IF arr(j) > arr(j + 1) THEN
                temp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = temp
                swapped = 1
            END IF
        NEXT j
        IF swapped = 0 THEN
            EXIT FOR
        END IF
    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 "     WORST-CASE BUBBLE SORT (reversed)"
    PRINT "============================================"
    PRINT ""
    n = 15
    FOR i = 0 TO n - 1
        arr(i) = n - i
    NEXT i
    PRINT "Before (reversed):"
    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
    FOR i = 0 TO n - 2
        FOR j = 0 TO n - 2 - i
            compCount = compCount + 1
            IF arr(j) > arr(j + 1) THEN
                temp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = temp
            END IF
        NEXT j
    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 "Worst-case comparisons: " + STR$(compCount)
    PRINT ""
    PRINT "============================================"
    PRINT "      COCKTAIL SHAKER SORT (bidirectional)"
    PRINT "============================================"
    PRINT ""
    n = 20
    FOR i = 0 TO n - 1
        arr(i) = ((i * 31 + 7) MOD 73) + 1
    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
    swapped = 1
    i = 0
    DO WHILE swapped = 1
        swapped = 0
        FOR j = i TO n - 2 - i
            IF arr(j) > arr(j + 1) THEN
                temp = arr(j)
                arr(j) = arr(j + 1)
                arr(j + 1) = temp
                swapped = 1
            END IF
        NEXT j
        IF swapped = 0 THEN
            EXIT DO
        END IF
        swapped = 0
        FOR j = n - 2 - i TO i + 1 STEP -1
            IF arr(j - 1) > arr(j) THEN
                temp = arr(j - 1)
                arr(j - 1) = arr(j)
                arr(j) = temp
                swapped = 1
            END IF
        NEXT j
        i = i + 1
    LOOP
    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 (checking sorted order):"
    i = 0
    DO WHILE i < n - 1
        IF arr(i) > arr(i + 1) THEN
            PRINT "FAIL: element " + STR$(i) + " > element " + STR$(i + 1)
        END IF
        i = i + 1
    LOOP
    PRINT "Done"
    FUNCTION = 0
END FUNCTION
