#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(100) AS LONG
    LOCAL output(100) AS LONG
    LOCAL counts(200) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL max_val AS LONG
    LOCAL min_val AS LONG
    LOCAL range_val AS LONG
    LOCAL bucket(100) AS LONG
    LOCAL bsize(10) AS LONG
    LOCAL b_idx AS LONG
    LOCAL bucket_size AS LONG
    LOCAL bucket_idx(10) AS LONG
    LOCAL num_buckets AS LONG
    LOCAL temp_str AS STRING
    LOCAL temp_val AS LONG

    PRINT "Counting Sort and Bucket Sort"
    PRINT "============================="
    PRINT ""

    ' Counting sort test
    n = 15
    arr(0) = 4
    arr(1) = 2
    arr(2) = 2
    arr(3) = 8
    arr(4) = 3
    arr(5) = 3
    arr(6) = 1
    arr(7) = 5
    arr(8) = 7
    arr(9) = 6
    arr(10) = 3
    arr(11) = 4
    arr(12) = 9
    arr(13) = 0
    arr(14) = 5

    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 "Counting sort 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

    i = 0
    WHILE i <= max_val
        counts(i) = 0
        i = i + 1
    WEND

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

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

    i = n - 1
    WHILE i >= 0
        counts(arr(i)) = counts(arr(i)) - 1
        output(counts(arr(i))) = arr(i)
        i = i - 1
    WEND

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(output(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "Counting sort after:  " + temp_str

    ' Verify
    i = 0
    temp_val = 1
    WHILE i < n - 1
        IF output(i) > output(i + 1) THEN
            temp_val = 0
        END IF
        i = i + 1
    WEND
    IF temp_val = 1 THEN
        PRINT "Counting sort verified"
    END IF

    ' Bucket sort
    n = 10
    arr(0) = 78
    arr(1) = 17
    arr(2) = 39
    arr(3) = 26
    arr(4) = 72
    arr(5) = 94
    arr(6) = 21
    arr(7) = 12
    arr(8) = 23
    arr(9) = 68

    PRINT ""
    PRINT "Bucket sort test:"
    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

    num_buckets = 4
    bucket_size = (max_val + num_buckets) / num_buckets
    IF bucket_size < 1 THEN bucket_size = 1

    i = 0
    WHILE i < num_buckets
        bsize(i) = 0
        bucket_idx(i) = 0
        i = i + 1
    WEND

    i = 0
    WHILE i < n
        b_idx = arr(i) / bucket_size
        IF b_idx >= num_buckets THEN b_idx = num_buckets - 1
        bucket(bsize(b_idx)) = arr(i)
        bsize(b_idx) = bsize(b_idx) + 1
        i = i + 1
    WEND

    ' Sort each bucket (simple insertion)
    i = 0
    WHILE i < num_buckets
        temp_val = 0
        WHILE temp_val < bsize(i)
            j = temp_val + 1
            WHILE j < bsize(i)
                IF bucket(i * 25 + j) < bucket(i * 25 + temp_val) THEN
                    b_idx = bucket(i * 25 + j)
                    bucket(i * 25 + j) = bucket(i * 25 + temp_val)
                    bucket(i * 25 + temp_val) = b_idx
                END IF
                j = j + 1
            WEND
            temp_val = temp_val + 1
        WEND
        i = i + 1
    WEND

    ' Concatenate buckets
    idx = 0
    i = 0
    WHILE i < num_buckets
        j = 0
        WHILE j < bsize(i)
            output(idx) = bucket(i * 25 + j)
            idx = idx + 1
            j = j + 1
        WEND
        i = i + 1
    WEND

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

    PRINT ""
    PRINT "Counting/bucket sort complete."

    FUNCTION = 0
END FUNCTION
