Home • News • GitHub • Wiki • Samples • InForm • GX • QBjs • Community • More...
' SORT.BAS
' by Antonio and Alfonso De Pasquale
' Copyright (C) 1994 DOS Resource Guide
' Published in Issue #17, September 1994, page 64
*****************************************************************************
SORT.BAS
by Antonio and Alfonso De Pasquale
Copyright (C) 1994 DOS Resource Guide
Published in Issue #17, September 1994, page 64
If you're in the habit of using QBasic arrays to store phone lists, personnel
information, sales figures, and the like, it's a sure bet that someday you'll
want to rearrange your data.
Maybe you'll need to list contacts by area code, or perhaps you'll want to
rank employees according to salary. Whatever the reason, you probably won't
want to spend hours to write and debug a sort routine. But if you add the two
subprograms BUBBLESORT and SHELLSORT contained in the program SORT.BAS to
your library of reusable code, lack of time won't pose a problem.
You can decide whether your situation calls for a bubble sort or a shell
sort, merge the appropriate subprogram with your existing QBasic program, add
a few lines of code, and get right down to the business of sorting your
arrays.
To run the program from the DOS command line and see a demonstration of the
sorting routines, change to the directory containing SORT.BAS, then type:
QBASIC /RUN SORT
What Are Arrays?
----------------
Arrays are tools for storing, organizing, and processing data efficiently in
a computer's memory. They're particularly handy for holding data items of the
same type and purpose.
For example, a calendar program might use arrays to hold the names of the
days of the week, the number of days in each month, and so on. From a
programming standpoint, it makes more sense to store the days of the week in
a single array than to declare a different variable for each day of the week.
Creating an array involves less coding and uses the computer's memory more
efficiently.
QBasic uses a DIM (for dimension) statement to declare arrays. The basic
syntax is the key word, DIM, followed by a parenthetical phrase that provides
the array's name and size. The following commands, for instance, declare two
arrays: a string array consisting of seven elements and a numeric array
consisting of 31 elements:
DIM DAY$(7)
DIM MONTHS(31)
QBasic lets you declare either numeric or string arrays. As the following
example shows, you may also use variables instead of numbers when declaring
the size of an array:
ARSIZE=250
DIM TOTAL(ARSIZE)
The first line sets the variable ARSIZE to 250; the second sets, or
dimensions, the array to the size specified by ARSIZE.
Bubble or Shell?
----------------
The simplest method of arranging the elements of a QBasic array is a bubble
sort. The procedure involves looking at adjacent elements in the array and
swapping their values when the elements are out of order. When you're sorting
values in ascending order, swapping values moves the largest values down the
array, permitting the smallest values to "bubble" to the top.
To sort data properly, the algorithm for a bubble sort must make several
passes through an array. The exact number of passes required is the total
number of elements in the array minus one. If your array contains 500 data
items, for instance, a bubble sort requires 499 passes to sort it properly.
As you might expect, a bubble sort is best suited for smaller arrays. The
algorithm, although easy to understand, is inefficient when working with
large arrays, because each element moves up or down by only one position in
each pass.
Named after its creator, Donald Shell, a shell sort provides a more efficient
method of processing larger arrays. Whereas a bubble sort compares and swaps
adjacent elements, the shell sort compares and swaps non-adjacent elements.
It begins by comparing the first element of the array with the middle
element, referred to as the gap. If no swap is made, the gap is halved and
non-adjacent elements are compared again. The gap is compared and halved
repeatedly until a swap is made.
Because this algorithm requires fewer comparisons in each pass through the
array, a shell sort arranges data more quickly than a bubble sort.
Consequently, a shell sort is superior to a bubble sort in most
circumstances. The bubble sort's only real advantages are that the routine is
compact and its logic is easy to follow. When working with moderate to large
arrays, the shell sort should be your routine of choice.
The SORT.BAS Program
--------------------
SORT.BAS shows how you might write subprograms to perform these two types of
sorts. The first part of the program prompts you for an array size, generates
an array of random numbers, and asks whether you want to perform a bubble or
a shell sort. The program then displays the starting and ending times of the
sort and displays the results on screen. This part of the listing is included
strictly for illustrative purposes. The meat of the listing is the pair of
subprograms, BUBBLESORT and SHELLSORT.
Using the Program
-----------------
To run the program if it is already loaded into QBasic, select Start from the
Run menu or press Shift-F5. You also may run the program from DOS by changing
to the directory containing SORT.BAS, and typing
QBASIC /RUN SORT
The screen will clear, and a greeting will appear. The program will then ask
you to specify the size of the array to be used for demonstrating the sort
routines, restricting the size to the range of 50 to 500 elements. Then the
program will take a few moments to create an array of randomly selected
numbers.
When the menu appears, you have three choices: pressing B to perform a bubble
sort, S to perform a shell sort, or Q to quit the program. When you press B
or S, the program displays the starting time and begins the sort. When
sorting is complete, the program displays the ending time. Press Enter to
view the sorted numbers on screen. As we mentioned earlier, a bubble sort is
best suited for small arrays; a shell sort dramatically improves performance
with larger arrays. When you specify large array sizes, you'll see the
dramatic advantage of the shell sort.
Creating a Sort Library
-----------------------
To use the two sorting subprograms in your own programs, you must first
isolate them from the original program and then add them to your code. Start
by using your mouse or the Shift keys in conjunction with the arrow keys to
highlight the sections of SORT.BAS that you don't need and delete them. Then,
use the File menu's Save As option to save the subprograms under a different
name, perhaps SORT.LIB. (You may save each subprogram separately, of course.)
Unfortunately, QBasic doesn't provide an import feature for merging
subprograms into a loaded program. You may use a DOS copy command such as the
following, however, to append the subprograms to your own QBasic code:
copy filename + sort.lib
Just substitute the name of your QBasic program for filename. This command
attaches the two subprograms to the bottom of your QBasic program. The next
time you call up QBasic and load your program, the proper declare statements
will automatically be added to your code, and the subprograms BUBBLESORT and
SHELLSORT will appear in the QBasic Subs list.
Of course, you may also simply type in the BUBBLESORT and SHELLSORT code into
your programs as needed. The above procedure saves you the effort of typing.
Calling the Functions
---------------------
Whether you want to perform a bubble sort or a shell sort, you must pass the
name of the array to be sorted to the subprogram. The following QBasic code
illustrates the proper syntax for calling the subprograms:
BUBBLESORT ARRAY1()
SHELLSORT ARRAY2()
In the first line, ARRAY1() is the name of the array; notice that you must
include the parentheses to inform QBasic that this variable refers to an
array. The subprogram then takes over and sorts the data in the stated array.
In the second line, ARRAY2() is the name of the array. In your own programs,
you may substitute any valid numeric array name for ARRAY1() and ARRAY2().
Further Modifications
---------------------
As written, the two sort subprograms are designed to arrange numeric data,
but you may modify them to work with string data (alphabetic characters), as
well. To do this, simply add a dollar sign ($) to the array name when
defining, declaring, or calling the subprograms. The dollar sign informs
QBasic that you're working with a string array rather than a numeric array.
Your declare statements, for example, would look like this:
DECLARE SUB BUBBLESORT (ARRAY$())
DECLARE SUB SHELLSORT (ARRAY$())
The first lines of the functions themselves would look like this:
SUB BUBBLESORT (ARRAY$())
.
.}more work done in these lines
.
SUB SHELLSORT (ARRAY$())
.
.}more work done in these lines
.
The code to call these routines would look like this:
BUBBLESORT ARRAY1$()
SHELLSORT ARRAY2$()
Those are the basics of working with arrays. Even if your QBasic programs
don't require sort routines right now, you might want to spend a little time
experimenting to make sure you grasp the fundamental rules. Then just tuck
the subprograms into your QBasic library for future reference.
Please note that QBjs is still in early development and support for these examples is extremely experimental (meaning will most likely not work). With that out of the way, give it a try!