! -- begin code
PRINT "start"
SET MODE "graphics"
SET BACK "blue"
SET COLOR "yellow"
CLEAR
ASK PIXELS mpx, mpy
SET WINDOW 1, mpx, 1, mpy
LET n= min(mpx, mpy)
DIM y(0)
MAT redim y(n)
CALL make_random (y())
CALL show_all_points(y())
! use only one of these subroutine calls per run
CALL unidirectional_bubble_sort(y())
! CALL bidirectional_bubble_sort(y())
PRINT "Done. Press a key. ";
GET KEY a
END
SUB unidirectional_bubble_sort(y())
LET n= ubound(y)
FOR i=1 to n-1
FOR j=i+1 to n
IF y(j)<y(i) then
CALL swap(i, j, y())
LET s= s + 1
END IF
NEXT j
NEXT i
PRINT s; "swaps in ";n; "points"
END SUB
SUB bidirectional_bubble_sort(y())
LET n= ubound(y)
IF y(j)>y(i) then ! comparison operator reversed
CALL swap(i, j, y())
LET s= s + 1
END IF
NEXT j
NEXT i
PRINT s; "swaps in ";n; "points"
END SUB
SUB show_all_points(y())
FOR i=1 to ubound(y)
PLOT POINTS: i, y(i)
NEXT i
END SUB
SUB swap(i, j, y())
CALL show_swap(i, j, y())
LET h= y(j)
LET y(j)= y(i)
LET y(i)= h
END SUB
SUB show_swap(i, j, y())
SET COLOR "blue"
PLOT POINTS: i, y(i)
PLOT POINTS: j, y(j)
SET COLOR "yellow"
PLOT POINTS: j, y(i)
PLOT POINTS: i, y(j)
END SUB
SUB make_random (y())
LET n= ubound(y)
FOR i=1 to n
LET y(i)= i
NEXT i
FOR i=1 to n
LET t = n - i + 1
LET t = int(rnd * t) + i
LET h = y(t)
LET y(t) = y(i)
LET y(i)= h
NEXT i
END SUB
! -- end code
there may be a zero-cost way to provide some level of
optimization: use a bidirectional scan through the list.
Cue the critics: "Don't use bubble sort."
With that out of the way ... there may be a zero-cost way to provide
some level of optimization: use a bidirectional scan through the list.
The program below in True Basic was inspired by the animation of a
selection sort here:
https://en.wikipedia.org/wiki/Selection_sort
The wiki animation for the bubble sort shows points sliding
horizontally into a line:
https://en.wikipedia.org/wiki/Bubble_sort
My inititial animation didn't look like the wiki animation ... because
I made both scans through the list in the same direction.
My initial animation showed a line approaching a curved front as
sorting sweeps values from the random field.
With the screen dimensions used for testing, the program processed 668 points.
The unidirectional scan required 113,532 swaps.
The bidirectional scan required "only" 40,165 swaps.
Note that the comparison operator needed to be reversed in this implementation of a bidirectional scan.
The call to the second sort routine is commented out in the code
below.
Only use one sort routine per run because it is uninteresting to call
the second sort after the first sort has already ordered the data.
! -- begin code
PRINT "start"
SET MODE "graphics"
SET BACK "blue"
SET COLOR "yellow"
CLEAR
ASK PIXELS mpx, mpy
SET WINDOW 1, mpx, 1, mpy
LET n= min(mpx, mpy)
DIM y(0)
MAT redim y(n)
CALL make_random (y())
CALL show_all_points(y())
! use only one of these subroutine calls per run
CALL unidirectional_bubble_sort(y())
! CALL bidirectional_bubble_sort(y())
PRINT "Done. Press a key. ";
GET KEY a
END
SUB unidirectional_bubble_sort(y())
LET n= ubound(y)
FOR i=1 to n-1
FOR j=i+1 to n
IF y(j)<y(i) then
CALL swap(i, j, y())
LET s= s + 1
END IF
NEXT j
NEXT i
PRINT s; "swaps in ";n; "points"
END SUB
SUB bidirectional_bubble_sort(y())
LET n= ubound(y)
FOR i=n-1 to 1 step -1
FOR j=2 to i
IF y(j)>y(i) then ! comparison operator reversed
CALL swap(i, j, y())
LET s= s + 1
END IF
NEXT j
NEXT i
PRINT s; "swaps in ";n; "points"
END SUB
SUB show_all_points(y())
FOR i=1 to ubound(y)
PLOT POINTS: i, y(i)
NEXT i
END SUB
SUB swap(i, j, y())
CALL show_swap(i, j, y())
LET h= y(j)
LET y(j)= y(i)
LET y(i)= h
END SUB
SUB show_swap(i, j, y())
SET COLOR "blue"
PLOT POINTS: i, y(i)
PLOT POINTS: j, y(j)
SET COLOR "yellow"
PLOT POINTS: j, y(i)
PLOT POINTS: i, y(j)
END SUB
SUB make_random (y())
LET n= ubound(y)
FOR i=1 to n
LET y(i)= i
NEXT i
FOR i=1 to n
LET t = n - i + 1
LET t = int(rnd * t) + i
LET h = y(t)
LET y(t) = y(i)
LET y(i)= h
NEXT i
END SUB
! -- end code
Wally,
there may be a zero-cost way to provide some level of
optimization: use a bidirectional scan through the list.
:-) Its not all that much of an optimalisation (though every bit helps),
and its cheating: the sorting does not "bubble" anymore.
What I mean? Use a small array (20 or so) and print each array result just >before swapping (all values on a single line), indicating both the i and j >positions. In the unidirectional sorting you will see the j position >"bubble" its way to the end.
Using your "opposite directions sort" you will see that that doesn't happen >anymore. :-|
But now the important question: Can you figure out *why* it doesn't happen
in your method ? (finding something like you did is terrific, but knowing >what/why it happens is the icing on the cake)
Another optimalisation (yeah, also cheating) is to only remember the
position of the lower (or higher) value and only swap just before the "next >i". The number of swaps than always equals the size of the array, minus >one. :-D
-- Origional message:
Wally W. <ww84wa@aim.com> schreef in berichtnieuws >c4ieqb1nklp07jd9505jef5nefp41j044d@4ax.com...
Cue the critics: "Don't use bubble sort."
With that out of the way ... there may be a zero-cost way to provide
some level of optimization: use a bidirectional scan through the list.
The program below in True Basic was inspired by the animation of a
selection sort here:
https://en.wikipedia.org/wiki/Selection_sort
The wiki animation for the bubble sort shows points sliding
horizontally into a line:
https://en.wikipedia.org/wiki/Bubble_sort
My inititial animation didn't look like the wiki animation ... because
I made both scans through the list in the same direction.
My initial animation showed a line approaching a curved front as
sorting sweeps values from the random field.
With the screen dimensions used for testing, the program processed 668
points.
The unidirectional scan required 113,532 swaps.
The bidirectional scan required "only" 40,165 swaps.
Note that the comparison operator needed to be reversed in this
implementation of a bidirectional scan.
The call to the second sort routine is commented out in the code
below.
Only use one sort routine per run because it is uninteresting to call
the second sort after the first sort has already ordered the data.
! -- begin code
PRINT "start"
SET MODE "graphics"
SET BACK "blue"
SET COLOR "yellow"
CLEAR
ASK PIXELS mpx, mpy
SET WINDOW 1, mpx, 1, mpy
LET n= min(mpx, mpy)
DIM y(0)
MAT redim y(n)
CALL make_random (y())
CALL show_all_points(y())
! use only one of these subroutine calls per run
CALL unidirectional_bubble_sort(y())
! CALL bidirectional_bubble_sort(y())
PRINT "Done. Press a key. ";
GET KEY a
END
SUB unidirectional_bubble_sort(y())
LET n= ubound(y)
FOR i=1 to n-1
FOR j=i+1 to n
IF y(j)<y(i) then
CALL swap(i, j, y())
LET s= s + 1
END IF
NEXT j
NEXT i
PRINT s; "swaps in ";n; "points"
END SUB
SUB bidirectional_bubble_sort(y())
LET n= ubound(y)
FOR i=n-1 to 1 step -1
FOR j=2 to i
IF y(j)>y(i) then ! comparison operator reversed
CALL swap(i, j, y())
LET s= s + 1
END IF
NEXT j
NEXT i
PRINT s; "swaps in ";n; "points"
END SUB
SUB show_all_points(y())
FOR i=1 to ubound(y)
PLOT POINTS: i, y(i)
NEXT i
END SUB
SUB swap(i, j, y())
CALL show_swap(i, j, y())
LET h= y(j)
LET y(j)= y(i)
LET y(i)= h
END SUB
SUB show_swap(i, j, y())
SET COLOR "blue"
PLOT POINTS: i, y(i)
PLOT POINTS: j, y(j)
SET COLOR "yellow"
PLOT POINTS: j, y(i)
PLOT POINTS: i, y(j)
END SUB
SUB make_random (y())
LET n= ubound(y)
FOR i=1 to n
LET y(i)= i
NEXT i
FOR i=1 to n
LET t = n - i + 1
LET t = int(rnd * t) + i
LET h = y(t)
LET y(t) = y(i)
LET y(i)= h
NEXT i
END SUB
! -- end code
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 309 |
Nodes: | 16 (2 / 14) |
Uptime: | 121:23:22 |
Calls: | 6,926 |
Files: | 12,388 |
Messages: | 5,436,852 |