Teochew Thunder: Web Tutorial: QBasic Bubble Sort Animation

Sorting data is one of the cornerstones of information technology. And the numero uno method, not in terms of ingenuity but in terms of sheer simplicity, is the Bubble Sort. How it works is simple.

Traverse a list of numbers, like the one below.

93,12,777,90

Each time you encounter a number, compare it with the number after that. If the first number is larger than the second number, swap their positions in the list. The numbers swapped are in red for clarity.

93,12,777,90

12,93,777,90

Carry on till you reach the end of the list, then begin anew at the beginning of the list. Do this till you have traversed the entire list, from first to last number, with no swaps taking place.

12,93,777,90

12,93,90,777

12,90,93,777

And thus, the list is sorted. Now, just for the heck of it, let's do this in QBasic! Here, we have a variable called sortlistsize which defines the number of numbers you wish to sort. This will be input by the user.

PRINT "T___T's BUBBLE SORT"
INPUT "What is the size of your list"; sortlistsize

After that, we use the number to define the size of the array sortlist, then use a For loop to ask the user to input all those numbers.

PRINT "T___T's BUBBLE SORT"
INPUT "What is the size of your list";

DIM sortlist(sortlistsize)

FOR i = 0 TO (sortlistsize - 1) STEP 1
INPUT "Please enter Number: ", sortlist(i)
NEXT i

If you run the code now, this is what you'll get.

After this, we define the variables col and row.

DIM sortlist(sortlistsize)

FOR i = 0 TO (sortlistsize - 1) STEP 1
INPUT "Please enter Number: ", sortlist(i)
NEXT i

DIM col, row

col = 2
row = 2

We're going to define four colors next - for the current numbers being sorted, and those not being sorted. For each category, we have a color for foreground and background. To find out what the values mean, look up the QBasic color chart.

DIM col, row

col = 2
row = 2

LOCATE row, col

DIM current_fc, current_bc
current_fc = 15
current_bc = 4

DIM unsorted_fc, unsorted_bc
unsorted_fc = 0
unsorted_bc = 14

Next, we define more variables. sorted is either 0 or 1, and is 1 only when the entire list has been sorted.
passes keeps track of the number of passes so far.
swaps keeps track of the number of swaps during the current pass. This value is reset in the next pass. currentpos keeps track of the cursor's current position in the sortlist array.
temp is a variable for holding the current value of the number to be swapped.
totalswaps, just for fun, shows us how many swaps it took for your list to get sorted.

DIM current_fc, current_bc
current_fc = 15
current_bc = 4

DIM unsorted_fc, unsorted_bc
unsorted_fc = 0
unsorted_bc = 14

DIM sorted, passes, swaps, currentpos, temp, totalswaps
sorted = 0
passes = 0
swaps = 0
totalswaps = 0
currentpos = 0

Here, we set the color to black and clear the screen using that color.

DIM sorted, passes, swaps, currentpos, temp, totalswaps
sorted = 0
passes = 0
swaps = 0
totalswaps = 0
currentpos = 0

COLOR 0, 0
CLS

This next While loop effectively means that the program continues execution till sorted becomes 1, which in turn means that the sortlist array has been completely sorted. Do not run your code at this time - you're only going to get an infinite loop because there's no exit clause.

COLOR 0, 0
CLS

WHILE sorted = 0

WEND

This introduces a slight pause that begins with every new pass. The cursor is then moved to the position on screen specified by row and col, which is, at the start of the loop, near the top left.

WHILE sorted = 0
SLEEP 2
LOCATE row, col
WEND

We're going to draw the entire series of numbers in the sortlist array on screen, in the appropriate colors. To do this, we use a For loop.

WHILE sorted = 0
    SLEEP 2
    LOCATE row, col

    FOR i = 0 TO (sortlistsize - 1) STEP 1

    NEXT i
WEND

Now, this next conditional checks if the variable i is at the current position of the cursor, or the next one. If so, it uses the current colors; otherwise it uses the default colors. The value is then drawn out on screen.

WHILE sorted = 0
    SLEEP 2
    LOCATE row, col

    FOR i = 0 TO (sortlistsize - 1) STEP 1
        IF i = currentpos OR currentpos + 1 = i THEN
            COLOR current_fc, current_bc
        ELSE
            COLOR unsorted_fc, unsorted_bc
        END IF

        PRINT sortlist(i);
    NEXT i
WEND

The color is changed back to black, and a space is printed as a separator.

After the entire list of numbers has been drawn on screen, we start sorting. Here, we provide an If conditional. If the number represented at the current position of the list represented by the variable currentpos is greater than the next...

...we swap their places with the use of the variable temp.

    IF sortlist(currentpos) > sortlist(currentpos + 1) THEN
        temp = sortlist(currentpos)
        sortlist(currentpos) = sortlist(currentpos + 1)
        sortlist(currentpos + 1) = temp
    END IF
WEND

We then increment the variable swaps, and tell the processor to pause for 1 second, just for effect.

We then go to the next line using the LOCATE command, and print out some information regarding the swap.

    IF sortlist(currentpos) > sortlist(currentpos + 1) THEN
        temp = sortlist(currentpos)
        sortlist(currentpos) = sortlist(currentpos + 1)
        sortlist(currentpos + 1) = temp

        swaps = swaps + 1

        SLEEP 1

        LOCATE row + 1, col
        COLOR 14, 0
        PRINT "Swapping ";
        PRINT temp;
        PRINT " with ";
        PRINT sortlist(currentpos);
        PRINT "...";
    END IF
WEND

And if no sort takes place, we clear the screen.

After that, we repeat the code block which was drawing the list of numbers. Yes I know, good programming practices dictate that I should write this as a function and avoid repeating myself. And I should, for the purposes of code efficiency, check if there are any swaps before redrawing. But honestly? This is pretty much throwaway code, so to hell with that.

    FOR i = 0 TO (sortlistsize - 1) STEP 1
        IF i = currentpos OR currentpos + 1 = i THEN
            COLOR current_fc, current_bc
        ELSE
            COLOR unsorted_fc, unsorted_bc
        END IF

        PRINT sortlist(i);
        COLOR 0, 0
        PRINT " ";
    NEXT i

    IF sortlist(currentpos) > sortlist(currentpos + 1) THEN
        temp = sortlist(currentpos)
        sortlist(currentpos) = sortlist(currentpos + 1)
        sortlist(currentpos + 1) = temp

        swaps = swaps + 1

        SLEEP 1

        LOCATE row + 1, col
        COLOR 14, 0
        PRINT "Swapping ";
        PRINT temp;
        PRINT " with ";
        PRINT sortlist(currentpos);
        PRINT "...";
    ELSE
   CLS
    END IF

    FOR i = 0 TO (sortlistsize - 1) STEP 1
        IF i = currentpos OR currentpos + 1 = i THEN
            COLOR current_fc, current_bc
        ELSE
            COLOR unsorted_fc, unsorted_bc
        END IF

        PRINT sortlist(i);
        COLOR 0, 0
        PRINT " ";
    NEXT i
WEND

The next block of code moves two lines down and prints stats.

    FOR i = 0 TO (sortlistsize - 1) STEP 1
        IF i = currentpos OR currentpos + 1 = i THEN
            COLOR current_fc, current_bc
        ELSE
            COLOR unsorted_fc, unsorted_bc
        END IF

        PRINT sortlist(i);
        COLOR 0, 0
        PRINT " ";
    NEXT i

    IF sortlist(currentpos) > sortlist(currentpos + 1) THEN
        temp = sortlist(currentpos)
        sortlist(currentpos) = sortlist(currentpos + 1)
        sortlist(currentpos + 1) = temp

        swaps = swaps + 1

        SLEEP 1

        LOCATE row + 1, col
        COLOR 14, 0
        PRINT "Swapping ";
        PRINT temp;
        PRINT " with ";
        PRINT sortlist(currentpos);
        PRINT "...";
    ELSE
        CLS
    END IF

    FOR i = 0 TO (sortlistsize - 1) STEP 1
        IF i = currentpos OR currentpos + 1 = i THEN
            COLOR current_fc, current_bc
        ELSE
            COLOR unsorted_fc, unsorted_bc
        END IF

        PRINT sortlist(i);
        COLOR 0, 0
        PRINT " ";
    NEXT i

    LOCATE row + 2, col
    COLOR 14, 0
    PRINT "Passes: ";
    PRINT passes;
    PRINT "Swaps: ";
    PRINT swaps;
WEND

And after printing out the stats, we increment the variable currentpos and then check if it has reached the end of the list. If so, we start tracking stats. The variable passes is incremented because getting to the end of the list counts as one pass completed. If no swaps have taken place during the entire pass, this means the list is sorted and the variable sorted can be set to 1. Otherwise, the number of swaps in this current pass is added to the running total.

    LOCATE row + 2, col
    COLOR 14, 0
    PRINT "Passes: ";
    PRINT passes;
    PRINT "Swaps: ";
    PRINT swaps;

    currentpos = currentpos + 1

    IF currentpos = sortlistsize - 1 THEN
        currentpos = 0
        passes = passes + 1

        IF swaps = 0 THEN
            sorted = 1
        ELSE
            totalswaps = totalswaps + swaps
        END IF

        swaps = 0
    END IF
WEND

So now we finally have a condition where the While loop can be exited. The next segment of code clears the screen in black and prints out the entire sort list, sans current marker.

WEND

COLOR 0, 0
CLS
LOCATE row, col

FOR i = 0 TO (sortlistsize - 1) STEP 1
    COLOR unsorted_fc, unsorted_bc
    PRINT sortlist(i);
    COLOR 0, 0
    PRINT " ";
NEXT i

And then we print out more stats to show how many passes and swaps it took to sort the list.

FOR i = 0 TO (sortlistsize - 1) STEP 1
    COLOR unsorted_fc, unsorted_bc
    PRINT sortlist(i);
    COLOR 0, 0
    PRINT " ";
NEXT i

LOCATE row + 2, col
COLOR 14, 0
PRINT "SORTED WITH PASSES: ";
PRINT passes;
LOCATE row + 3, col
PRINT "TOTAL SWAPS: ";
PRINT totalswaps; s

Enjoy your sorting! Run your code. Enter in the size of your list followed by the numbers, then watch the magic unfold.

Note!

List sizes of 1 and 0 are automatically considered sorted. However, this has not been handled in the code, so if you try it, you're likely to break something. I just want to point out that this isn't a great practice as far as programming goes. I figure we can get away with it today because we're just messing about with QBasic and a Bubble Sort. Very trivial stuff.

Thanks, guys. I had a great time. Sort of.
T___T

Teochew Thunder

Pages

Tuesday, 5 July 2016

Web Tutorial: QBasic Bubble Sort Animation

Note!

No comments:

Post a Comment

Teochew Thunder

Upcoming Web Tutorials

Features

Reviews