Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.lang.basic.misc > #431

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

Show all headers | View raw

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

Back to comp.lang.basic.misc | Previous | Next — Next in thread | Find similar

Thread

Fun with sorting -- two animations for bubble sort -- zero-cost optimization Wally W. <ww84wa@aim.com> - 2016-08-07 11:01 -0400
  Re: Fun with sorting -- two animations for bubble sort -- zero-cost optimization Wally W. <ww84wa@aim.com> - 2016-08-07 12:49 -0400
  Re: Fun with sorting -- two animations for bubble sort -- zero-cost optimization "R.Wieser" <address@not.available> - 2016-08-07 19:32 +0200
    Re: Fun with sorting -- two animations for bubble sort -- zero-cost optimization Wally W. <ww84wa@aim.com> - 2016-08-07 16:53 -0400
      Re: Fun with sorting -- two animations for bubble sort -- zero-cost optimization Wally W. <ww84wa@aim.com> - 2016-08-07 18:02 -0400

csiph-web