Chapter Nine
Sorting
Keyword: SWAP
Here is our solution to the standard deviation program:
LET ITEMS = 100
DIM A(ITEMS)
RANDOMIZE TIMER/3
FOR NUM = 1 TO ITEMS
LET A(NUM) = INT(26*RND) + 25
NEXT NUM
FOR NUM = 1 TO ITEMS
LET SUM = SUM + A(NUM)
NEXT NUM
LET AVE = SUM / ITEMS
FOR NUM=1 TO ITEMS
LET SQUARE = SQUARE + ((AVE-A(NUM))^2)
NEXT NUM
LET SQUARE = SQUARE / ITEMS
PRINT"Standard deviation is";SQR(SQUARE)
END
Did you spot our little trick with the DIM command? We first defined how many items we would have in our list. Then we dimensioned the array with a variable in line 2. We also used that same variable (ITEMS) in all of our FOR...NEXT loops that cycle through the array. Now we can easily change the number of items that we are "standard deviating" simply by changing line 1. Or you could replace line 1 with an INPUT statement to have the user specify how many items to be generated. Also, if you want to see just what a standard deviation does, try changing the range of the random numbers generated in line 5. Instead of using 26*RND, try 51*RND and 6*RND and see what you get for a standard deviation. You will notice that as the data is less scattered, the standard deviation will drop way down.
Were you able to write any kind of a sort program? If you did, congratulations. If you didn't, don't feel bad; it isn't as easy as it sounds. In this chapter, we are going to walk through the development of the program piece by piece. The first thing we need to do is clear out any program in memory. Now we have a clean slate to start off with. The very first thing we need to do is tell the computer how many items we will be sorting. All of those items will be stored in one array. Let's use the trick that we used in the standard deviation program. First, we assign the number of items we will be generating and sorting to the variable ITEMS. Then we will dimension the array A using the variable ITEMS. Our first two lines will look like this for generating fifty items:
LET ITEMS = 50 DIM A(ITEMS)
Now that we have that out of the way, let's seed our random number generator:
RANDOMIZE TIMER/3
Next, we will generate the random numbers and place them into our array using a FOR...NEXT loop. Leave a blank line or two between this section and the previous one:
FOR NUM = 1 TO ITEMS
LET A(NUM) = INT(100 * RND) + 1
NEXT NUM
Can you guess from that second line what range our random numbers will be in? They will range from 1 to 100. Now that we have all of our numbers stored into the array, we need to sort them. We will do it in ascending order. Do you recall how to do a pass through the array? You compare the first item in the array with all of the remaining items, one at a time. This sounds like a wonderful place for a FOR...NEXT loop, doesn't it? Yes it does. It looks like one loop ought to do the trick. It does, but only for the first pass. If you remember, the second pass compares the second element to all remaining ones, and the third pass compares the third element to all remaining ones, and so on. It sounds like another loop would come in handy here. That is correct. But you say we have two loops going at the same time? That is an ideal case for a pair of nested loops. Let's see, we will compare the first element of the array on only one pass, and our outer loop will always begin with the first element. So our loop would begin with FOR OUTER=1 TO something. When we get to the end of the array, do we have to compare the last element to itself to see if it is less than itself? No! So our complete loop statement would look like this (type it in):
FOR OUTER = 1 TO ITEMS - 1
Now what about our inner loop? As you recall, we compare the element in question with every succeeding element in the array. This means for our first pass, we start the inner loop with the second element. Hmmm, It sounds like we would use a FOR INNER = 2 TO something. That won't work, however, When we get to the second pass, we want to start with the third element, so our inner loop would look like FOR INNER = 3 TO something. Now what can we use for the changing starting point? Wait a minute! The outer loop's variable indicates which element is being tested for the largest! Why don't we start our inner loop with one more than what our outer loop is currently at? That is exactly what we need to do, so our inner loop will look like FOR INNER = OUTER + 1 TO something. Where does our inner loop end? Well, when we were scanning the array, we always went to the end of the array. What variable is holding the value for the length of the array? Right! It's ITEMS. Our complete FOR statement will look like this (Type it in):
FOR INNER = OUTER + 1 TO ITEMS
Now we need to figure out what the comparison between our two variables needs to be for us not to swap the elements around (you'll see why we asked it this way later). We are sorting in an ascending order, so if the first element is less than or equal to the "later on down the line" element, there is no need to swap, so we will skip over our programming code to exchange the two elements in the array. Can you figure out the IF...THEN command that we will use (without the line label after the THEN, of course)? It will look like this (type it in):
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGE
Now let's go ahead and finish up our loops with the necessary NEXT statements. Can you guess which will come first; INNER or OUTER? Try to guess without looking at the lines below. I know it's hard, what with them being in a nice bold type. Go ahead and enter these lines (we need the label for a certain reason):
NOCHANGE:
NEXT INNER
NEXT OUTER
QBASIC has a command to exchange two variables, and we will be needing it here. Way back in the early days of BASIC (before the IBM PC's and such - Apple II, Radio Shack TRS-80, Commodore PET, any CP/M- based computer, etc.), such a command did not exist. The way to swap two variables was to put one in a temporary variable, put the second into the first, and then put the temporary into the second. That took up three lines. So what is this new, magical command, you ask? Well, it's the (hold onto your hat!) SWAP command! How does it work? Instead of explaining it, let's type in the actual program line (It's the one in color):
FOR OUTER = 1 TO ITEMS - 1
FOR INNER = OUTER + 1 TO ITEMS
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGE
SWAP A(OUTER), A(INNER)
NOCHANGE:
NEXT INNER
NEXT OUTER
Yes, there really is a Santa Claus! Basically, the command takes the form SWAP A, B where A and B are variables. In our case, we are using array elements - two different elements of the same array. Well, let's get back to the program. It is actually in a working form right now, but if you run it, the computer will go away for about a second and then give you the "Press any key to continue" message, meaning that it's finished. Why? We don't have any PRINT statements in it! Let's print out the sorted array using a FOR...NEXT loop (add this to the end of what we have so far):
FOR NUM = 1 TO ITEMS
PRINT A(NUM),
NEXT NUM
END
Don't forget that comma at the end of the PRINT command! We will be printing out 50 numbers, and we want them all to fit on the screen! Now go ahead and run the program. Remember that the PRINT command prints from left to right, then top to bottom. The numbers will all be in ascending order. If they are not, check your typing carefully, especially for lines:
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGEand
SWAP A(OUTER), A(INNER)
How do you know that the sort is really working? Maybe the numbers are being generated in the correct order mysteriously! Well, not so! Would you like to see what the array looks like before it is sorted? Add the green line, and don't forget the comma:
LET ITEMS = 50
DIM A(ITEMS)
RANDOMIZE TIMER / 3
FOR NUM = 1 TO ITEMS
LET A(NUM) = INT(100 * RND) + 1
PRINT A(NUM),
NEXT NUM
Now run the program. Do you see a problem? That's right, the sorted list starts right after the unsorted list. Do you know why? It's because of the comma at the end of line 70. It leaves the next print position on the same line, so when the PRINT command at the bottom comes along, it takes up where it left off earlier. In this case, however, there are 50 items that are printed out in 5 columns, so the comma does send the next print position down to the next line. How do we fix that? Do you remember the very first thing we did with the print command? If not, go back to chapter one and review. Now we are actually going to put that theory into a real program! Here is the line:
FOR OUTER = 1 TO ITEMS - 1
FOR INNER = OUTER + 1 TO ITEMS
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGE
SWAP A(OUTER), A(INNER)
NOCHANGE:
NEXT INNER
NEXT OUTER
PRINT
FOR NUM = 1 TO ITEMS
PRINT A(NUM),
NEXT NUM
END
Now run the program again. See our blank line between the two lists? It kind of separates the two, doesn't it? Let's spruce up our output a little bit more. Right now, the computer operator would only see two lists of numbers. Why don't we print out what the computer is showing us? Let's add these PRINT commands:
LET ITEMS = 50
DIM A(ITEMS)
RANDOMIZE TIMER / 3
PRINT "Unsorted List:"
FOR NUM = 1 TO ITEMS
LET A(NUM) = INT(100 * RND) + 1
PRINT A(NUM),
NEXT NUM
PRINT "Sorting..."
FOR OUTER = 1 TO ITEMS - 1
FOR INNER = OUTER + 1 TO ITEMS
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGE
SWAP A(OUTER), A(INNER)
NOCHANGE:
NEXT INNER
NEXT OUTER
PRINT
PRINT "Sorted List:"
FOR NUM = 1 TO ITEMS
PRINT A(NUM),
NEXT NUM
END
Now go ahead and run the program again. Looks a little nicer, doesn't it?
Let's do one more thing to this program. We'll print out the pass number that the sorting routine is executing. Can you figure out how to do it? Here are the changes to make:
LET A(NUM) = INT(100 * RND) + 1
PRINT A(NUM),
NEXT NUM
PRINT "Sorting Pass:"
FOR OUTER = 1 TO ITEMS - 1
PRINT OUTER;
FOR INNER = OUTER + 1 TO ITEMS
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGE
SWAP A(OUTER), A(INNER)
NOCHANGE:
Now run the program, and watch it go. Run it several times, and see how the list is correctly sorted every time? When you are through having fun with this program, make sure that you save it to disk (call it SORT), because we will be using it again in the next few chapters to learn more ways of formatting the screen's output.
For your reference, here is our entire sort program. You may use this listing
to check your typing:
LET ITEMS = 50
DIM A(ITEMS)
RANDOMIZE TIMER / 3
PRINT "Unsorted List:"
FOR NUM = 1 TO ITEMS
LET A(NUM) = INT(100 * RND) + 1
PRINT A(NUM),
NEXT NUM
PRINT "Sorting Pass:"
FOR OUTER = 1 TO ITEMS - 1
PRINT OUTER;
FOR INNER = OUTER + 1 TO ITEMS
IF A(OUTER) <= A(INNER) THEN GOTO NOCHANGE
SWAP A(OUTER), A(INNER)
NOCHANGE:
NEXT INNER
NEXT OUTER
PRINT "Sorted List:"
FOR NUM = 1 TO ITEMS
PRINT A(NUM),
NEXT NUM
END
Here are a few things for you to practice your programming skills with:
The median of a list of numbers is that element such that when the numbers are sorted, half of the numbers lie above it, and half of the numbers lie below it. This happens only when there are an odd number of items in the list. If there are an even number of items, the median is the average of the middle two numbers. Have the program use an INPUT command to specify the number of items with a maximum of 200. Use input range checking. The only output necessary for this program is the median value.
Using the sorting program we developed this chapter, change it so that the numbers generated range between 1 and 1000.
Change the original sorting program so that it generates 150 items.
Change the original sorting program so that the list is sorted in descending order.
We'll give you the answers next time. Also in the next chapter, we will introduce some commands that will help you in making "custom" output displays for your program, including how to clear the screen, and how to print a character or number in a particular position. See you then!!
Introduced in this chapter:
Keywords: SWAP
Concepts: Dimensioning an array from a variable, A
sorting algorithm, Using PRINT commands to enhance a program's operation.
