#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(100) AS LONG
    LOCAL output(100) AS LONG
    LOCAL counts(10) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL max_val AS LONG
    LOCAL exp_val AS LONG
    LOCAL digit_val AS LONG
    LOCAL bucket(100) AS LONG
    LOCAL bucket_count AS LONG
    LOCAL idx AS LONG
    LOCAL temp_str AS STRING
    LOCAL temp_val AS LONG

    n = 12
    arr(0) = 170
    arr(1) = 45
    arr(2) = 75
    arr(3) = 90
    arr(4) = 2
    arr(5) = 802
    arr(6) = 24
    arr(7) = 66
    arr(8) = 170
    arr(9) = 45
    arr(10) = 75
    arr(11) = 90

    PRINT "Radix Sort (LSD Base-10)"
    PRINT "======================="
    PRINT ""

    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

    ' Find max value
    max_val = 0
    i = 0
    WHILE i < n
        IF arr(i) > max_val THEN max_val = arr(i)
        i = i + 1
    WEND

    exp_val = 1
    WHILE max_val / exp_val > 0
        i = 0
        WHILE i < 10
            counts(i) = 0
            i = i + 1
        WEND

        i = 0
        WHILE i < n
            digit_val = (arr(i) / exp_val) MOD 10
            counts(digit_val) = counts(digit_val) + 1
            i = i + 1
        WEND

        i = 1
        WHILE i < 10
            counts(i) = counts(i) + counts(i - 1)
            i = i + 1
        WEND

        i = n - 1
        WHILE i >= 0
            digit_val = (arr(i) / exp_val) MOD 10
            counts(digit_val) = counts(digit_val) - 1
            idx = counts(digit_val)
            output(idx) = arr(i)
            i = i - 1
        WEND

        i = 0
        WHILE i < n
            arr(i) = output(i)
            i = i + 1
        WEND

        exp_val = exp_val * 10
    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
    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"
    ELSE
        PRINT "NOT sorted"
    END IF

    ' Test with larger set
    n = 10
    arr(0) = 99
    arr(1) = 54
    arr(2) = 27
    arr(3) = 81
    arr(4) = 12
    arr(5) = 36
    arr(6) = 63
    arr(7) = 45
    arr(8) = 18
    arr(9) = 72

    PRINT ""
    PRINT "Set 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

    max_val = 0
    i = 0
    WHILE i < n
        IF arr(i) > max_val THEN max_val = arr(i)
        i = i + 1
    WEND

    exp_val = 1
    WHILE max_val / exp_val > 0
        i = 0
        WHILE i < 10
            counts(i) = 0
            i = i + 1
        WEND

        i = 0
        WHILE i < n
            digit_val = (arr(i) / exp_val) MOD 10
            counts(digit_val) = counts(digit_val) + 1
            i = i + 1
        WEND

        i = 1
        WHILE i < 10
            counts(i) = counts(i) + counts(i - 1)
            i = i + 1
        WEND

        i = n - 1
        WHILE i >= 0
            digit_val = (arr(i) / exp_val) MOD 10
            counts(digit_val) = counts(digit_val) - 1
            idx = counts(digit_val)
            output(idx) = arr(i)
            i = i - 1
        WEND

        i = 0
        WHILE i < n
            arr(i) = output(i)
            i = i + 1
        WEND

        exp_val = exp_val * 10
    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

    PRINT ""
    PRINT "Radix sort complete."

    FUNCTION = 0
END FUNCTION
