Hi Arryman,
Your routine has one serious flaw (which you actually see in your posted example, which "loses" the initial 3 and introduces an extra 0), and one inefficiency you might want to be aware of:
1) The serious flaw is that BBC BASIC arrays are 0-based (that is, there is an element 0): if you assign content with a statement like
a%() = 5,3,7,9,1,12
The 5 gets put in a%(0), which would never get sorted by your routine, which starts with an index of 1.
On the other hand, many people use their arrays starting from position 1 - so if you corrected this flaw, you would find yourself sorting a%(0) (which would be 0) into the intended data. That won't be a problem if all your data are positive (or at least non-negative) numbers, but would be if there are negative numbers in the data, since one of them will get sorted into position 0 (and "lost to follow-up", as the doctors say), while a stray 0 would appear in your data!
You will note that the library sort routine offers the option to handle this by passing it array(1) when you call it. You might want to amend your routine to have a parameter that determines whether it considers the array as 0-based or 1-based (or indeed, if it offers the option to sort only a subset of the array, as the library one does.
2) The inefficiency is that your structure, using a flag to check for any changes, but looping through the whole array each time, can be even more inefficient that a standard bubble sort, because after the n'th pass we know that the top n elements are the largest in the array: we don't need to check them again. While this doesn't change the overall complexity of the routine (it's still O(n^2) - in other words it grows in length by the square of the number of elements), it could take roughly twice as many comparisons (think of it as working down the leading diagonal of the "square", but only doing the top half).
On the other hand, your system using a flag can save a lot of time if the array is already almost sorted, since you stop as soon as there are no more swaps.
I tend to implement bubble sorts "the other way up", i.e. putting the lowest in place first:
Code: Select all
DIM a%(15)
a%() = 3,4,5,6,7,10,8,7, 20, 12, 45, 67, 66, 29,42,45
PROC_showContents
REM Note correction to remove the space between procedure name and bracket
REM I think your version only worked because you used the same (global) name for the array inside the procedure
PROC_sort(a%(),0)
PROC_showContents
END
REM Note my version sorts the LOWEST values first (More intuitive for the nested loops)
REM Note that passing arrays in and getting them back relies on "pass by reference"
REM - it wouldn't work to change a "normal" variable (unless you used RETURN)
DEFPROC_sort(a%(),base%)
LOCAL x%,y%,size%
size% = DIM(a%(),1)
FOR x% = base% TO size%-1
FOR y%=x%+1 TO size%
IF a%(x%)>a%(y%) THEN SWAP a%(x%),a%(y%)
NEXT y%
NEXT x%
ENDPROC
DEF PROC_showContents
size% = DIM(a%(),1)
REM Note change to start from a%(0)
FOR s% = 0 TO size%
PRINT a%(s%);
NEXT s%
PRINT
ENDPROC
Best wishes,
D
(it's certainly not my intension to be negative), I played around with it and included a loop counter - in both of ours. The WHILE loop, as a minimum, takes at least the same number as the nested FOR loop. In fact, occasionally, it loops twice the number. It's an interesting concept and one to play with.