' Selection Sort — repeatedly finds minimum element from unsorted portion
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(1000) AS LONG
    LOCAL original(1000) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL minIdx AS LONG
    LOCAL temp AS LONG
    LOCAL compCount AS LONG
    LOCAL swapCount AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    LOCAL minVal AS LONG
    n = 50
    PRINT "============================================"
    PRINT "        SELECTION SORT DEMONSTRATION"
    PRINT "============================================"
    PRINT ""
    PRINT "Original array:"
    PRINT ""
    FOR i = 0 TO n - 1
        arr(i) = ((i * 13 + 7) MOD 97) + 1
        original(i) = arr(i)
    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
    swapCount = 0
    FOR i = 0 TO n - 2
        minIdx = i
        minVal = arr(i)
        FOR j = i + 1 TO n - 1
            compCount = compCount + 1
            IF arr(j) < minVal THEN
                minVal = arr(j)
                minIdx = j
            END IF
        NEXT j
        IF minIdx <> i THEN
            temp = arr(i)
            arr(i) = arr(minIdx)
            arr(minIdx) = temp
            swapCount = swapCount + 1
        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 "Comparisons: " + STR$(compCount) + "  Swaps: " + STR$(swapCount)
    PRINT ""
    PRINT "============================================"
    PRINT "     SELECTION SORT ON REVERSE DATA"
    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
    swapCount = 0
    FOR i = 0 TO n - 2
        minIdx = i
        FOR j = i + 1 TO n - 1
            compCount = compCount + 1
            IF arr(j) < arr(minIdx) THEN
                minIdx = j
            END IF
        NEXT j
        IF minIdx <> i THEN
            temp = arr(i)
            arr(i) = arr(minIdx)
            arr(minIdx) = temp
            swapCount = swapCount + 1
        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 "Comparisons: " + STR$(compCount) + "  Swaps: " + STR$(swapCount)
    PRINT ""
    PRINT "============================================"
    PRINT "    SELECTION SORT ON ALREADY-SORTED DATA"
    PRINT "============================================"
    PRINT ""
    n = 15
    FOR i = 0 TO n - 1
        arr(i) = i + 1
    NEXT i
    PRINT "Before (already 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
    swapCount = 0
    FOR i = 0 TO n - 2
        minIdx = i
        FOR j = i + 1 TO n - 1
            compCount = compCount + 1
            IF arr(j) < arr(minIdx) THEN
                minIdx = j
            END IF
        NEXT j
        IF minIdx <> i THEN
            temp = arr(i)
            arr(i) = arr(minIdx)
            arr(minIdx) = temp
            swapCount = swapCount + 1
        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 "Comparisons: " + STR$(compCount) + "  Swaps: " + STR$(swapCount)
    PRINT ""
    PRINT "============================================"
    PRINT "   DUAL SELECTION (min and max at once)"
    PRINT "============================================"
    PRINT ""
    n = 20
    FOR i = 0 TO n - 1
        arr(i) = ((i * 19 + 3) MOD 67) + 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
    i = 0
    DO WHILE i < n / 2
        minIdx = i
        minVal = arr(i)
        j = i
        DO WHILE j < n - i
            IF arr(j) < minVal THEN
                minVal = arr(j)
                minIdx = j
            END IF
            j = j + 1
        LOOP
        IF minIdx <> i THEN
            temp = arr(i)
            arr(i) = arr(minIdx)
            arr(minIdx) = temp
        END IF
        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:"
    i = 0
    DO WHILE i < n - 1
        IF arr(i) > arr(i + 1) THEN
            PRINT "FAIL at position " + STR$(i) + ": " + STR$(arr(i)) + " > " + STR$(arr(i + 1))
        END IF
        i = i + 1
    LOOP
    PRINT "Selection sort complete"
    FUNCTION = 0
END FUNCTION
