The text for this tutorial, the BASIC program, and a
practice CSV file for sorting, can be downloaded as a ZIP file from the JB
Archives website, http://jbusers.com/phpBB/index.php All topics available will be displayed
when your browser is opened, but files for download will only be listed to
REGISTERED USERS WHO ARE LOGGED IN.
Sorting, sorting, sorting... thousands, perhaps millions
of hours of computer time are devoted to sorting data into ordered lists. When I first approached the Newsletter Sorting
Challenge, I planned to create four arrays for the NL#, topic, author, and
program compatibility. The sortFile.csv
for the challenge contained 740 records with 4 fields each. The finished program should be able to sort
by keying on any field within the file.
Being only a modestly skilled amateur coder, I pulled out
my trusty bubble sort algorithm and quickly dashed off a program to sort and
display the data in the file. Hmmm, only
11 seconds per sort, not bad - but definitely not good. Could I find a better way?
To see a comparison of several sorting methods, download
Willie Lee's sorting demo from
http://babek.info/libertybasicfiles/lbf_dnload_notice.php?file=sort_willie_lee.zip
In practical applications, the QuickSort is the fastest
type of sort available to beginning coders, but how in the heck do you write
the code? First I had to find the code,
available in LB Newsletter #75.
QuickSort was originally published by C.A.R. Hoare in Computer Journal
(1962). This version was updated by
David Szfranski for LB in 1998, and is adapted for my FUNCTION jbSORT later in
the tutorial. How fast is the sort? Would you believe 740 records of 4 fields
each in an average of 200 milliseconds?
[code]
' updated 08/31/98 by David
Szafranski
' The Quick Sort version
presented here avoids recursion, and instead uses
' a local array as a form of
stack. This array stores the upper and
lower
' bounds showing which section
of the array is currently being considered.
' Another refinement added is to
avoid making a copy of elements in the
' array. As the Quicksort progresses, it examines one
element selected
' arbitrarily from the middle of
the array, and compares it to the elements
' that lie above and below
it. To avoid assigning a temporary copy
this
' version simply keeps track of
the selected element number.
first = 1: last = nmbrOfItems
zed = int(last/5 + 10)
REDIM QStack(zed)
flag = 1
stackptr = 0
'DO
while flag <> 0
'
DO
WHILE first <
last
xVar = int(last/2)+int(first/2)
temp = theArray(xVar) '*This is the name of the array.
I = first: J =
last
' do
flag1 = 1
while I <= J and flag1 <> 0
WHILE theArray(I) < temp
I = I + 1
wend
WHILE theArray(J) > temp
J = J - 1
wend
' IF I > J
THEN EXIT DO
if I > J then flag1 = 0 : goto [skip]
' IF I < J
THEN SWAP theArray(I), theArray(J)
' = = = = = = = = = This is the
"meat" of the swap! = = = = = = = =
if I < J then
temp1 = theArray(I)
temp2 = theArray(J)
theArray(I) = temp2
theArray(J) = temp1
end if
' = = = = = = Adaptations go
between these lines. = = = = = = = = =
I = I + 1
J = J - 1
[skip]
wend
'
IF I < last
THEN
QStack(stackptr) = I
QStack(stackptr + 1) = last
stackptr = stackptr + 2
END IF
last = J
wend
'
LOOP WHILE first < last
'
IF stackptr = 0 THEN EXIT DO
if stackptr = 0 then flag = 0 : goto [skipit]
stackptr = stackptr - 2
first = QStack(stackptr)
last = QStack(stackptr + 1)
'
[skipit]
wend
REDIM QStack(0) 'ERASE QStack
return
[/code]
DISCLAIMER: Is it
legal to copy another man's code and use it in my own program?
Legally and morally, it is my understanding I am not
allowed to use the work of another for commercial purposes, and I am not
allowed to take credit for the work and claim it as my own. Now that we've gotten that out of the way,
let's get to work adapting David's code for use as jbSORT FUNCTION.
Studying Qsort, we see David's code is for a
single-dimensioned numeric array. This
won't do. In this demo we're going to
sort topCities.csv, which I compiled from data found at www.factmonster.com and
contains the name, size, and population of the top 50 cities in the
The first thing we need to do is open topCities.csv and
count the records in the field so we can DIM cities$(x,y). The following code does this for us.
[code]
OPEN "topCities.csv" FOR INPUT AS #1
WHILE EOF(#1)=0
LINE INPUT #1,
dummy$ 'Count
the number of records.
records=records+1
WEND
CLOSE #1
PRINT "There are ";records;"
records in the file."
PRINT
DIM cities$(records,3)
[/code]
After dimensioning, we can load the array with this code.
[code]
OPEN "topCities.csv" FOR INPUT AS #1
WHILE EOF(#1)=0
cnt=cnt+1
'Load cities$() with all values from the data file as string
values.
INPUT #1, city$ : cities$(cnt,1)=city$
INPUT #1, area$
WHILE LEN(area$)<4 : area$="0"+area$ : WEND
cities$(cnt,2)=area$
INPUT #1, pop$
WHILE LEN(pop$)<8 : pop$="0"+pop$ : WEND
cities$(cnt,3)=pop$
WEND
CLOSE #1
[/code]
WAIT A MINUTE!
Cities are strings, but area and population are numeric values. Why did you put them in as strings? Have you ever tried to put metric components
on a
Duhhh, well, yeah, I know that, but why are you padding
the strings with leading zeros with multi-statement WHILE/WEND loops?
A very good question. When JB (even LB for that matter) sorts
string data, the data is ordered according to ASCII value. Sorting by ASCII value means a city with an
area of 47 sq/mi will be listed AFTER a city of 356
sq/mi, clearly a mistake on the part of the coder. If we pad the string value with leading
zeros, 0047 will be less than 0356, and the array will be properly sorted. The same reasoning applies to the population
data.
In this CSV file, I know all cities have an area less
than 1,000 sq/mi, but I padded the area$ to 4 characters just in case. The largest pop$ value is 7 characters for
[code]
begin=TIME$("ms")
any=jbSORT(cnt,
finish=TIME$("ms")
[/code]
After the data has been loaded, we begin the jbSORT
function. Before doing so, the program
gets the time from the computer clock.
After the sort, we'll get the time again and use (finish-begin) to
determine the time required for the sort.
When running this program on my computer, a P-4 with clock speed of 2.8
GHz, sort time is less than 15 milliseconds and is frequently reported as zero.
To print the sorted data to the MAINWIN, I used this
routine:
[code]
PRINT "City"; TAB(24);"Sq/Mi";
TAB(35);"Population"; TAB(48);"Persons sq/mi"
FOR k=1 to cnt
popSqMi= INT(VAL(cities$(k,3))/VAL(cities$(k,2))) 'Divide pop by area
PRINT cities$(k,1); TAB(24); USING("###",cities$(k,2)); _
TAB(37); USING("#######",cities$(k,3)); TAB(50);
USING("######",popSqMi)
NEXT k
PRINT
[/code]
FOR k=1 to cnt will print the data in ASCENDING
order. If the user wants to display the
data in DESCENDING order, it must be changed to
[code]
FOR k=cnt TO 1 STEP -1
[/code]
FUNCTION jbSORT is customized as follows:
[code]
FUNCTION jbSORT(cnt,
first = 1
last = cnt 'How many items are in the array to be
sorted?
zed = INT((last/5)+10)
DIM qstack(zed)
flag = 1
stackptr=0
while flag<>0
while first < last
xVar = INT((last/2)+INT(first/2)) 'Choose a pivot point in the array.
temp$ = cities$(xVar,
i = first
j = last
flag1 = 1
while i <= j and flag1 <> 0
while cities$(i,
i = i + 1
wend
while cities$(j,
j = j -1
wend
if i > j then flag1 = 0 : goto [skip]
if i < j then
' = = = = = = = = This is
"the meat" of the swap! = = = = = = = =
' = = = = = = = = The current
values of the array = = = = = = = =
temp1$
= cities$(i,1) 'name
temp2$
= cities$(j,1)
temp3$
= cities$(i,2) 'area
temp4$
= cities$(j,2)
temp5$
= cities$(i,3) 'pop
temp6$ = cities$(j,3)
' = = = = = = = = Swap these
array values = = = = = = = = = = = =
cities$(i,1) = temp2$
cities$(j,1) = temp1$
cities$(i,2) = temp4$
cities$(j,2) = temp3$
cities$(i,3) = temp6$
cities$(j,3) = temp5$
' = = = = = = = = End of needed
modifications = = = = = = = = = =
END IF
i = i+1
j = j-1
[skip]
wend
if i < last then
qstack(stackptr) = i
qstack(stackptr+1) = last
stackptr = stackptr + 2
end if
last = j
wend
if stackptr=0 then flag=0 : goto [skipit]
stackptr=stackptr-2
first=qstack(stackptr)
last=qstack(stackptr+1)
[skipit]
wend
REDIM qstack(0) 'Erases the array
END FUNCTION
[/code]
jbSORT will order the array
beginning with row 1, and sort on column
After passing the information to jbSORT, the Worbles
begin doing their incredible job. If you
are unfamiliar with the history of the Worble society, please download
SortChallengeDemo.zip from http://jbusers.com/phpBB/viewtopic.php?t=47 and go
to the HELP file. You must be logged in
as a registered user before downloading.
The goings on inside the function are
very confusing to a self-taught coder like me, so I had a lengthy discussion
with my Chief Worble to gain more insight.
When the parameters are passed to the
function, the Worbles leap into action, first dividing into two teams, RED and
BLUE. I thought the Chief Worble
meant Republicans and Democrats but he quickly corrected me. The Worble teams are RED and BLUE striped,
similar to honey bees. "But how can
you tell the REDs from the BLUEs," I asked. "It's simple," he answered,
"the REDs begin with a red stripe on top, and the BLUEs have a blue stripe
on top." Since Worbles are
spherical in shape, I guess it all depends upon your point of view.
The Worbles have an (I) team on one side of the CPU, and
a (J) team on the other. The Chief
Worble compares the value of (i) to (j) and if a swap is needed, each team
grabs a string and races it to the goal on the other side of the CPU. (See The Worble Connection regarding Worble
speeds) Because there are thousands and
thousands of team members, many strings can be carried in rapid succession. "But what keeps them from bumping into
each other when they reach the center," I asked? "Oh, we solved that problem ages ago
when connecting to USB devices with a USB hub.
We have very tiny traffic cops directing traffic to the correct device. Within the CPU, the job is much easier
because the distances are less."
I had to ask.
The efficiency of the QuickSort is immensely increased
because when a RED or BLUE Worble has reached the far side, each joins the
opposing team and runs to the opposite goal with the next value to be
sorted! "Then how can you keep
score," I asked? "We measure
success by how fast the complete task can be finished," Mr. Chief Worble
told me. "We don't place any value
on the scores of separate teams, because the job at hand is more
important."
Okay, to avoid stupid looks on my face, I won't ask any
more questions. It sounds to me as if
our politicians should drop partisan politics and adopt the philosophy of
Worbles. Perhaps I should vote
"Demolican" next election? Or
would that be "Republicrat?"
When modifying the QuickSort code, we began with temp$(i)
and temp$(j) for comparison. Because our
new array has 3 columns, we must allow for temp$(i,1), temp$(i,2), and
temp$(i,3). These values represent the
current values in the array, and must be compared to temp$(j,1)
through temp$(j,3).
After any needed swaps have been made, we do a little
housekeeping and diminish the value of (i) and (j) so the distance the Worbles
run grows less each time. What prevents
them from crashing together like Hockey teams at the Stanley Cup, I don't know,
and this time I didn't ask.
You can copy and use jbSORT function in any programs you
write, as long as you make the needed changes for cnt,
Because I am not a politician, I will not attempt to take
credit for the above code, I only "stole it fair
and square!" The real work has been
done by the Worbles.