Some
Techniques
Program Design 1
2
3
4
5
Declare array colour$
Read colours into
the
array
FOR
item
~
2mS
LET p =
item
LET comp$ = colour$(p)
REPEAT compare
IF
comp$ > = cOlour$(p-1) : EXIT compare
LET colour$(p)
= colour$(p-1)
LET p
~
p-1
END REPeat compare
LET colour$(p)
~
comp$
END FOR
item
PRINT sorted array colour$
DATA
•
MODIFIED
PROGRAM
Further testing
reveals
a fault
It
anses
very
easily
if
we
have
data
in
which the
first
item
IS
not
in
its
correct position
at
the
start.
A simple change
of
initial
data
to:
red black blue magenta green
cyan
yellow white
reveals
the
problem.
We
compare black
with
red
and decrease p
to
the
value,
1.
We
come round again and try
to
compare black with a vanable colour$(p-I) which
is
colour$(O)
which does not exist
This
is
a well-known problem
In
computing and the solution
is
to
"post a sentinel"
on
the
end
of
the
array.
Just before entering
the
REPeat loop
we
need:
LET colour$(O)
= comp$
Fortunately,
SuperBASIC
allows
zero subscripts, otherwise the problem would have
to
be solved
at
the expense
of
readability.
100
REM
Insertion
Sort
110
DIM
colour$(8,7l
120
FOR
item
= 1
TO
8:
READ
coLour$(item)
130
FOR
item
= 2
TO
8
140
LETp=item
150
LET
comp$
=
coLour$(p)
160
LET
colour$(Q)
=
comp$
170
REPeat
compare
180
IF
comp$
>=
coLour$(p-1)
:
EXIT
compare
190
LET
coLour$(p)
=
colour$(p-1)
200
LET
p =
p-1
210
END
REPeat
compare
220
LET
colour$(p)
=
comp$
230
END
FOR
item
240
PRINT
"Sorted
...
" I
colourS
250
DATA
"black",
"blue",
lImagenta",
"red"
260
DATA
"green
ll
,
"cyan",
"ye
llow",
"wh;
te"
•
•
COMMENT
1.
The program works
well.
It
has been
tested
with
awkward data:
AAAAAAA
BABABAB
ABABABA
BCDEFGH
GFEDCBA
98
2.
An
insertion sort
is
not
particularly
fast,
but
it
can
be
useful
for adding a
few
items
to
an
already sorted list
It
is
sometimes convenient
to
allow modest amounts
of
time frequently
to
keep items
in
order rather
than
a substantial amount
of
time
less frequently
to
do a complete re-sorting.
You
now
have
enough background knowledge
to
follow a development
of
the
handling
of
the
file
of
seven
names and telephone numbers.
12/84
•
To Next Page
Loading...
Need help?
General
