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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

! -- 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

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

Uploaded animations as gif files:

https://i.imgsafe.org/7acebe5cd5.gif = curved front

https://i.imgsafe.org/7ad040ded1.gif = sweeping line

https://i.imgsafe.org/7acf49d7e7.gif = wiki method

https://i.imgsafe.org/7acfc6795a.gif = 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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


-- 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Sun, 7 Aug 2016 19:32:44 +0200, R.Wieser wrote:

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

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.

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.

-- 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)