Fun with sorting -- two animations for bubble sort -- zero-cost optimization

[Wally W.]

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 W.]

On Sun, 07 Aug 2016 11:01:30 -0400, Wally W. wrote:

Loop limits were wrong in bidirectional scan. Corrected by replacing
the two relevant lines below.

The swap count increased to 40,478.

Post by Wally W.
! -- 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 to 2 step -1
FOR j=1 to i-1

Post by Wally W.
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

[R.Wieser]

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

Regards,
Rudy Wieser

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
https://en.wikipedia.org/wiki/Selection_sort
The wiki animation for the bubble sort shows points sliding
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 W.]

Post by R.Wieser
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.

Thanks for your interest. I was confused how the wiki animation for
"bubble sort" knew to place the pixel in the lowest-left corner so
early.

My first attempt to sort high values first produced a sweeping line,
not a gathering line.

This routine (plugged into the larger program) provides an animation
of the random field being ordered into a sweeping line:

SUB sweeping_bubble_sort(y())
LET n= ubound(y)
FOR i=n-1 to 1 step -1
FOR j=n to i+1 step -1
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

Post by R.Wieser
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)

The credit for the method goes to wiki user Nmnogueira, who made a
number of animations:
https://en.wikipedia.org/wiki/User:Nmnogueira#Image_Self-made

I was trying to replicate his animation for bubble sort.

I like the aesthetics, if not the efficiency, of the method that shows
order pushing back a curved front of disorder.

The sweeping animation is curious, but I don't think it is as much fun
to watch.

Post by R.Wieser
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

If I understand correctly, this is a "selection sort."

I made a routine to animate that. It was so fast that a 'pause'
statement was needed to watch it run. It doesn't give the full feel of
the algorithm because it isn't allowed to accelerate at the end.

SUB selection_sort(y())
LET n= ubound(y)
FOR i=1 to n-1
LET t= y(i)
LET k= i
FOR j=i to n
IF y(j)<t then
LET t= y(j)
LET k= j
END IF
NEXT j
PAUSE 0.01
CALL swap(i, k, y())
NEXT i
END SUB

It is "more of the same" compared with the wiki animation. It is
aesthetically interesting because the line pushes a shrinking square
of randomness into order. It also increases the density of points in
the random field by a small amount as it shrinks the square.

I'm afraid I can't say much about *why* the bidirectional "bubble
sort" isn't really a *bubble* sort anymore. It seems to be looking
ahead and finding things the unidirectional sort can't know yet, such
as "the lowest value anywhere" as opposed to "the lowest value so
far."

Thanks again for your interest and comments.

Post by R.Wieser

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
https://en.wikipedia.org/wiki/Selection_sort
The wiki animation for the bubble sort shows points sliding
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 W.]

On Sun, 07 Aug 2016 16:53:42 -0400, Wally W. wrote:

Uploaded animations as gif files:

Loading Image... = curved front

Loading Image... = sweeping line

Loading Image... = wiki method

Loading Image... = selection sort

The gifs were made with program from here:
http://www.codeplex.com/

It seems good. It is portable -- no cursed "installation" required.

The poor aiming of the capture window is my fault. I didn't redo them
because the interesting parts seem to be visible in the gifs.

Recommend opening the images in Chrome or Internet Explorer. I tried
Ifranview, but there were ghosts in the image.

The gif files don't capture the real-time behaviour exactly.

For that, get the True BASIC Bronze demo:
http://www.truebasic.com/free_and_demos