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,93,90,777
12,90,93,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.
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);
COLOR 0, 0
PRINT " ";
NEXT i
WEND
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...
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
END IF
WEND
...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.
IF sortlist(currentpos) > sortlist(currentpos + 1) THEN
temp = sortlist(currentpos)
sortlist(currentpos) = sortlist(currentpos + 1)
sortlist(currentpos + 1) = temp
swaps = swaps + 1
SLEEP 1
END IF
WEND
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.
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
WEND
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
