On Tue, 17 Jun 2003, Daniel Serpell wrote:

> On Sat, 14 Jun 2003, Mike Harrison wrote:
> > For such a small number of values, maybe some trickery can be done to
> > simplfy things, in particular it may be easier to insert new values in
> > the correct place in the list instead of sorting afterwards - a new
> > value cannot affect the order of the other 4 values. Also, it may be
> > easier/quicker to not move the values about, just keep a list of what
> > order they need to be in, as this can be held in one byte per entry, so
> > fewer things need to be juggled about
>
> For such low number of items, bubble sort is the best. You need an
> algorithm like (in pseudo C):
>
> #define try_swap(a,b) if( a > b ) { int x=a; a=b; b=x; }
>
>     try_swap(a[0],a[1]);
>     try_swap(a[0],a[2]);
>     try_swap(a[0],a[3]);
>     try_swap(a[0],a[4]);
>
>     try_swap(a[1],a[2]);
>     try_swap(a[1],a[3]);
>     try_swap(a[1],a[4]);
>
>     try_swap(a[2],a[3]);
>     try_swap(a[2],a[4]);
>
>     try_swap(a[3],a[4]);
>
> It's unroled, so you don't really need array access (you can
> sort any five variables). To write in PIC assembler, you only
> need the "try_swap" macro. If your variables were 8 bit, it
> can be done in 6 cicles, so the total is  6*10 = 60 cycles.


Is this what you're thinking:

     movf   b,W
     subwf  a,W
     skpnc
      goto  L1

   ; a is greater than b, so swap
   ; note, W = b-a

     addwf  a,f   ; a = (b-a) + a ==> b
     subwf  b,f   ; b = b - (b-a) ==> a

L1:


This would be 6 cycles worst case and 5 best case.


However, for sorting 5 items there are faster ways of doing this unrolled
loop. For example, for 4 items:


    try_swap(a[0],a[1]);
    try_swap(a[2],a[3]);

    if(a[1] < a[2]) {
      swap(a[1], a[2]);

      try_swap(a[0],a[1]);
      try_swap(a[2],a[3]);
    }

Or effectively 5 try_swaps instead of 6 worst case and about 3 tryswaps
best case. (15 cycles best case and 30 worst case).


For 5 items, it's a little more complicated.

    // sort the first 4
    try_swap(a[0],a[1]);
    try_swap(a[2],a[3]);

    if(a[1] < a[2]) {
      swap(a[1], a[2]);

      try_swap(a[0],a[1]);
      try_swap(a[2],a[3]);
    }


    if(a[2] < a[4]) {
      swap(a[2], a[4]);
      try_swap(a[1],a[2]);
      try_swap(a[0],a[1]);

    }

    try_swap(a[3],a[4]);



~4.5 tryswap's best case and 9 worst case compared to the 10 of a bubble
sort. (28 cycles best case, 54 worst case compared to 50 best and 60 worst
case cycles for the bubble sort).

Scott

--
http://www.piclist.com hint: To leave the PICList
mailto:piclist-unsubscribe-request@mitvma.mit.edu