• Fun with sorting -- two animations for bubble sort -- zero-cost optimiz

    From Wally W.@21:1/5 to All on Sun Aug 7 11:01:30 2016
    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)
  • From Wally W.@21:1/5 to All on Sun Aug 7 12:49:00 2016
    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)
  • From Wally W.@21:1/5 to All on Sun Aug 7 18:02:27 2016
    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)
  • From R.Wieser@21:1/5 to Wally W. on Sun Aug 7 19:32:44 2016
    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)
  • From Wally W.@21:1/5 to R.Wieser on Sun Aug 7 16:53:42 2016
    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)