Help with decision maths question

[gerard@dugdill.com]

I have an exercise for decision maths A level, albeit the book is 10-15 years old. I want to know how to run these programs, to compare interchange sort and bubble sort. There are two programs below, top one interchange and bottom one bubble. In the book I am using it lists both programs side by side and says "investigate which is quicker for different data sets and varying levels of disorder".

So it lists both programs (see below) and then it says: "The input will be the same for both".

READ n
DIM L(n)
FOR i = 1 TO n : READ L(i) ; NEXT i
DATA

where "DATA is the value of n followed by the list of numbers to be sorted.

Then "Output can be achieved with: FOR i - 1 TO n : PRINT L(i) : NEXT i"

So do I:

copy in both programs
then the last section "READ n"
then add a list of numbers somewhere
then add the code section about printing?

Here are the two programs:

FIRST ONE (INTERCHANGE)

FOR i = 1 TO n - 1
minpos = i
FOR j = i + 1 TO n
IF L(j) < L(minpos) THEN minpos = j
NEXT j
temp = L(i)
L(i) = L(minpos)
L(minpos) = temp
NEXT i

SECOND ONE (BUBBLE)

FOR i = 1 TO n - 1
swapflag = 0
FOR j = i + 1 TO n – i
IF L(j) > L(j + 1) THEN temp = L(j)
L(j) = L(j + 1)
L(j + 1) = temp
swapflag = 1
NEXT j
IF swapflag = 0 THEN i = n – 1
NEXT i

Many thanks for any help.

[Richard Russell]

So do I:

copy in both programs
then the last section "READ n"
then add a list of numbers somewhere
then add the code section about printing?

I would say it's purely a matter of preference, there is no 'right' or 'wrong' way. If it was me I'd put both routines in the same program, simply for the convenience of working with one program rather than two, but I wouldn't want to be prescriptive.

As for ensuring both routines are supplied with the same set of numbers, using READ/DATA would be a perfectly reasonable way. An alternative you could consider is using the Pseudo Random Number Generator but 'seeding' it so that it generates the same sequence of numbers every time.

A potential advantage of that approach is the ease of increasing the size of the list, which could be relevant since you're asked to "investigate which is quicker" and you will be needing to sort thousands of items to make it slow enough to compare with any accuracy.

Alternatively you might want to run each routine a large number of times as a way of making it slow enough to measure.

[Richard Russell]

As for ensuring both routines are supplied with the same set of numbers, using READ/DATA would be a perfectly reasonable way. An alternative you could consider is using the Pseudo Random Number Generator but 'seeding' it so that it generates the same sequence of numbers every time.

Yet another method would be to fill a 'master' array with the set of numbers, which you never subsequently change, and copy that into the 'array to be sorted' each time:

Code: Select all

REM FIRST ONE (INTERCHANGE)
L() = master()
FOR i = 1 TO n - 1
...

REM SECOND ONE (BUBBLE)
L() = master()
FOR i = 1 TO n - 1
...

[nvingo]

Consider also that sets with partially-ordered elements may favour one method over the other. Extreme sets such as reverse-ordered should show both methods at their limits.
You can use the RESTORE statement to start READing at a particular DATA set, prior to populating the array.

[gerard@dugdill.com]

Hi. I am just starting with:

FOR i = 1 TO n - 1
minpos = i
FOR j = i + 1 TO n
IF L(j) < L(minpos) THEN minpos = j
NEXT j
temp = L(i)
L(i) = L(minpos)
L(minpos) = temp
NEXT i

READ n
DIM L(n)
FOR i = 1 TO n : READ L(i) ; NEXT i
DATA 4,2,3,1,4
FOR i= 1 TO n: PRINT L(i) : NEXT i

trying to specify a list with 4 numbers, followed by the actual four numbers.
I just keep getting "no such variable" when I try to run the program.

Thanks,

[Richard Russell]

I just keep getting "no such variable" when I try to run the program.

Not surprising: the variable n, used in the first line, is not yet declared!

In case you're not already doing so, run the program in Debug mode - the line which is triggering the error will be highlighted.

[gerard@dugdill.com]

Ok, I'll give it a go.

I am just a beginner, although I did have a BBC comp in about 1983, with an old manual, but never made it to Computer Studies O level.

Guys, thanks all for your help, it's much appreciated.

kr

[nvingo]

Hi. I am just starting with:

FOR i = 1 TO n - 1
minpos = i
FOR j = i + 1 TO n
IF L(j) < L(minpos) THEN minpos = j
NEXT j
temp = L(i)
L(i) = L(minpos)
L(minpos) = temp
NEXT i

READ n
DIM L(n)
FOR i = 1 TO n : READ L(i) ; NEXT i
DATA 4,2,3,1,4
FOR i= 1 TO n: PRINT L(i) : NEXT i

trying to specify a list with 4 numbers, followed by the actual four numbers.
I just keep getting "no such variable" when I try to run the program.

Thanks,

You have the code there, but you have the sorting routine before the routine to create the dataset.
Just swap them to test the code, I appreciate it's a work-in-progress and the debugged code will be used elsewhere.

[gerard@dugdill.com]

So you're saying just swop the two main chunks of text so it reads

(first chunk)

READ n
DIM L(n)
FOR i = 1 TO n : READ L(i) ; NEXT i
DATA 4,2,3,1,4

(and then second chunk)

FOR i = 1 TO n - 1
minpos = i
FOR j = i + 1 TO n
IF L(j) < L(minpos) THEN minpos = j
NEXT j
temp = L(i)
L(i) = L(minpos)
L(minpos) = temp
NEXT i

(followed by the print instructions)?

FOR i= 1 TO n: PRINT L(i) : NEXT i

Thanks

[Richard Russell]

So you're saying just swop the two main chunks of text

That's one way, but perhaps more in the 'spirit' of your original program would be to leverage procedures to retain the 'out of order' nature of the code:

Code: Select all

PROCinit
PROCsort
PROCprint
END

DEF PROCsort
FOR i = 1 TO n - 1
minpos = i
FOR j = i + 1 TO n
IF L(j) < L(minpos) THEN minpos = j
NEXT j
temp = L(i)
L(i) = L(minpos)
L(minpos) = temp
NEXT i
ENDPROC

DEF PROCinit
READ n
DIM L(n)
FOR i = 1 TO n : READ L(i) ; NEXT i
DATA 4,2,3,1,4
ENDPROC

DEF PROCprint
FOR i= 1 TO n: PRINT L(i) : NEXT i
ENDPROC

It's very much a matter of coding 'style' rather than right or wrong. I've not had any formal Computer Science education but I'm keenly aware of the 'modern' programming paradigms such as encapsulation. That would make me uneasy about accessing too many global variables in a procedure, and since initialisation typically involves declaring global variables my preference is to do that 'inline' rather than in a subroutine.

Of course one could go to the extent of passing the 'global' variables as parameters, but whilst that fits with the encapsulation paradigm it's in my view unnecessarily complicated and contrived, especially in a case when there are many more global variables requiring declaration than there are here:

Code: Select all

PROCinit(n, L())
...

DEF PROCinit(RETURN n, RETURN L())
LOCAL i
LOCAL DATA
RESTORE +1
READ n
DIM L(n)
FOR i = 1 TO n : READ L(i) ; NEXT i
DATA 4,2,3,1,4
ENDPROC