Classic Computer Magazine Archive BEST OF ANTIC VOLUME 1

Bubble Sort


This is a handy Sort Utility intended to be called from Basic and allows you to sort almost anything that can fit in your computer's memory. The flexibility of the Sort should cover many applications. Records may be any size up to 256 bytes. The sort fields may be any size up to the length of the record. You can sort on as many different fields as you need, and each field can be independently sorted in ascending or descending sequence.

The sorting technique is the traditional Bubble Sort which works by looking through a file of records in memory, and comparing the sort field of each record to the one following it. If any two adjacent records are not in sequence, the sort will exchange the positions of those two records. The sort continues to scan the file until there are no more records to exchange. In this way, records with the higher sort fields get pushed towards the end of the file, and records with the lower sort fields get pushed towards the beginning of the file. All of this takes place in memory so that it appears that the records BUBBLE into place.

The Sort only requires 182 bytes and the machine language is relocatable, therefore you can load and execute this sort anywhere in memory. Although you can put the Sort in any program you like, your file size is going to be limited by available memory. For large files, it is best to write a small Basic program that contains only this Sort, a String large enough to hold your file, and whatever Basic statements it takes to load a file, call the Sort and write out the new sequenced file.

Although the Sort works very fast, its speed can be improved by about 30% by turning Antic off. Just before calling the sort, save the value at PEEK(559) then POKE in a zero. All this does is shut down the screen display, but in so doing, it makes about 30% more CPU cycles available to the Sort. After the sort, POKE the saved valued back into 559 and the screen display will turn back on.

All sort parameters are passed to the Sort in the Basic USR call in the following sequence: 1. Address of the String containing the file. 2. Length of the records. 3. Number of records to be sorted. The next parameters specify the fields to be sorted by; 4.1. Position of the first byte of the field. 4.2. Length of the field. 4.3. '0' for ascending sequence, or '1' for descending sequence. Sort Fields are specified in Major to Minor order. That is, if you want to sort on State, and Zip Code within State, then State is the Major order and should be the first set of Sort Field parameters. The only limitation on the number of sort fields is the number of parameters that fit in the Basic statement calling the Sort.

The program in Listing 2 loads the machine language code for the Sort in Lines 1 to 9. The rest of the program demonstrates one of many techniques that can be used to read an unsequenced file, sort and rewrite a sequenced file. Type and run the program and, at the prompt, enter the first and last names of about 9 friends. The first names will be sorted ascending, the last names will be sorted descending and then displayed on the screen.

By Adrian Dery

Listing 1: BUBBLE1.BAS Download

Listing 2: BUBBLE2.SRC Download / View