Number Sort Algorithm - Page 2


+ Reply to Thread
Page 2 of 2 FirstFirst 12
Results 41 to 55 of 55
  1. #41
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Default

    Quote Originally Posted by aratti View Post
    Hi Darrel, I tested the sorting snippet you have posted, using a rather interesting swapping technique.
    The code worked, but now and than, it was yielding very fanny results.
    From a closer code analysis, I came to the conclusion that :
    Code:
    If CounterA > 0 then CounterA=CounterA-2
    should be corrected with:
    Code:
    If CounterA > 1 then CounterA=CounterA-2
    After the correction, I didn't see any fanny result for the rest of my testing period.
    The explanation I have given is the following:

    If CounterA = 1 then CounterA - 2 = 255 and this screw up everything.

    Can you confirm?

    Al.
    Well, I wouldn't think it's a problem.
    Right after the IF block that statement is in, Melanie put a ...

    CounterA=CounterA+1

    So if CounterA = 1, subtracting 2 makes it 255, then adding 1 makes it 0 again.

    Had you made any other changes?
    <br>
    DT

  2. #42
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    Had you made any other changes?
    Yes, a second one, but more for cleaning the code, since it didn't effect functionality:

    Code:
    RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)
    Has been cleaned with:

    Code:
    RawData(CounterA+1) = RawData(CounterA) ^ RawData(CounterA+1)

    Well, I wouldn't think it's a problem.
    Right after the IF block that statement is in, Melanie put a ...

    CounterA=CounterA+1

    So if CounterA = 1, subtracting 2 makes it 255, then adding 1 makes it 0 again
    But the above make sense, I do better check the whole system again.

    Thank you Darrel.

    Al.
    Last edited by aratti; - 19th December 2009 at 19:16.
    All progress began with an idea

  3. #43
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default fleshing out the sort

    WOW, must be a good day!
    I remembered Melanie had a comment on sorting out changing inputs, but I couldn't find my bookmark for it. I went to the main forum page and there it was on the right column!
    Whew! someone must be looking out for me....

    My situation involves reading WORD sized data every 30ms (with quite a few spurious readings) and controlling a PWM output with somewhere near a 2-3 second response to drive some mechanicals that require slow reaction. I have been trying to mold Darrel's DT_Average16 routine to make it work, but with little success in this application.

    Can someone elaborate a bit on feeding fresh data into this sort and trimming the top and bottom readings? I don't understand how to run this with a continuous data stream without blowing up the sort.

    Thanks
    Bo

  4. #44
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default

    Here is what I have come up with so far.....
    it is getting closer.
    Derived from Malanie's suggestion about parsing data and DT's averaging scheme * PIC18F2525 @ 8 MHz
    Code:
    ByteData var byte                                                                                                      
    CounterA    var word             ' sort counter
    CounterB    var byte
    CounterC    var byte
    DataA       var word             ' storage for sorted values
    DatSort     var byte             ' pointer to middle 8 values
    DatAvg      var word             ' averaged value of sorted data
    RawData     var word[16]         ' storage for raw data
    Clear
    AvgCount	CON  8		         ' = Number of samples to average
    FAspread	CON  1000	         ' = Fast Average threshold +/-
    INCLUDE "AllDigital.pbp"
    DEFINE OSC 8
    OSCCON = %01110000
    DEFINE HSER_RCSTA 90h ' Enable serial port & continuous receive
    DEFINE HSER_TXSTA 24h ' Enable transmit, BRGH = 1
    DEFINE HSER_CLROERR 1 ' Clear overflow automatically
    DEFINE HSER_SPBRG 34  ' 57600 Baud @ 8MHz, -0.79%
    SPBRGH = 0
    BAUDCON.3 = 1         ' Enable 16 bit baudrate generator
    
    hserout["SortAverage",10,13]
    pause 500
    goto Start
    
    'Sort Array SUB ** collects 16 readings, sorts, and averages middle 8 ******
    SortArray:
        CounterA=0
    SortLoop:                          ' sorts 16 readings of RawData in order
        If RawData(CounterA+1) < RawData(CounterA) then
            DataA=RawData(CounterA)
            RawData(CounterA)=RawData(CounterA+1)
            RawData(CounterA+1+0)=DataA
            If CounterA > 0 then CounterA=CounterA-2
            endif
        CounterA=CounterA+1
        If CounterA < 15 then goto SortLoop
    '    for CounterC = 0 to 15        ' These three lines O/P the sort results
    '    hserout["Ordered[",dec CounterC,"]= ", dec RawData[CounterC],10,13] 
    '    next CounterC
    '**** Trim and Average ***************************************************
       for DatSort = 4 to 11                    ' pick out middle 8 readings
        IF ABS (DatAvg - RawData[DatSort]) > FAspread Then CatchUp
        IF ABS (DatAvg - RawData[DatSort]) < AvgCount Then RealClose
        DatAvg = DatAvg - (DatAvg/AvgCount)
        DatAvg = DatAvg + (RawData[DatSort]/AvgCount)
        GoTo AVGok
      CatchUp:
        DatAvg = DatAvg + (RawData[DatSort]/8)  ' catch-up by 1/8 value of reading
        GoTo AVGok
      RealClose:
        DatAvg = DatAvg - (RawData[DatSort]/(AvgCount/4))
        DatAvg = DatAvg + (DatAvg/(AvgCount/4))
      AVGok:
    ' hserout["Middle[",dec datsort,"] = ",dec RawData[DatSort],10,13] 'SHOW mid 8
       next DatSort
        Return  
    '** END SUB************************
    Start:
          FOR CounterB=0 to 15
         HSERIN [RawData[CounterB]]
          NEXT CounterB      
          FOR CounterB=0 to 15
          HSEROUT["RawData[",DEC counterB,"] = ",DEC rawdata[CounterB],10,13]
          NEXT CounterB
          CALL SortArray
          HSEROUT ["Sorted Averaged result ",dec DatAvg,10,13]
         GOTO start

  5. #45
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    Code:
    for DatSort = 4 to 11                    ' pick out middle 8 readings
     DatAvg = DatAvg + RawData[DatSort]
    NEXT DatSort
    
    DatAvg = DatAvg >>3
    Return
    You can short and semplify your averaging routine with the above example. DatAvg sums up the 8 central values then you devide by 8 for the average.

    Al.
    All progress began with an idea

  6. #46
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default

    Hi Al. Thanks for looking at it.

    I like the way you simplified, but my concern was that since I will be working with WORD data, the result of the addition could get big enough that I would have to use LONGs if I didn't use DT's running average scheme.

    So far, I have only tested it with byte data, and it does seem to settle slowly on something close to average. I need to try WORD data and see how that works.

    Bo

  7. #47
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    ... but my concern was that since I will be working with WORD data, the result of the addition could get big enough that I would have to use LONGs...
    Using a 10 bits adc, the maximun number you can obtain is 1023. Now summing up 8 readings of 1023 each, you will end up with your word variable at 8184 (overflow will occur at 65K)

    Since you are using adc , you have to remove
    Code:
    INCLUDE "AllDigital.pbp"
    from your code.

    Al.
    All progress began with an idea

  8. #48
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default clarification

    Hi Al,
    Thanks for engaging in this thread. Sometimes when one posts and gets no response, you begin to worry if your question is so off the wall that no one is interested.

    The values that I'm working with are actually timer values that are WORD sized. The ultimate result is measuring ultrasonic pulse return to calculate distance. In the real program, I'm using a comparator interrupt to grab of the values. That one uses the analog, but here I'm just trying to sort out the averaging scheme.
    The response needs to be smoothed considerably due to the high instance of random response of the ultrasonics. The values go on to determine the PWM output that drive a servo valve that controls some heavy hydraulics that can't tolerate quick movement. The response time needs to be in the 2-3 second range with smooth changes to work well. Since the values are 0-65535, and readings every 30mS, I'm trying to use Melanie's suggestions to dump the extremes, and DT's averaging to get away from LONGs and 32 bit math.

    Current testing is with a second PIC generating the return pulse timing to separate the circuit from the program so that I can find the weakness. I'm trying to send a serial in to simulate the echo numbers. The next step is to convert the RX bytes into WORDS and see if the program works correctly.

    Back to Burn and Turn
    Bo

  9. #49
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default A workaround to avoid long

    Hi Bo,
    clear now. One workaround for not using long and still average them in the conventional way is the following:

    Code:
    RawData[0] = 0
    for DatSort = 4 to 11                               ' pick out middle 8 readings
    RawData[0] = RawData[0]  + (RawData[DatSort] - RawData[3])    ' extract the total difference
    NEXT DatSort
    RawData[0] = RawData[0]  >>3               ' average the total difference
    DatAvg =  RawData[0]  + RawData[3]       ' add the average difference to the subtractor
    Return
    You addup in RawData[0] all the differences , then you average them and finally you add them to the RawData[3], the subtractor.

    Al.
    All progress began with an idea

  10. #50
    Join Date
    Mar 2003
    Location
    Commerce Michigan USA
    Posts
    1,166

    Default

    Al, I'm confused..... Where does RawData[3] come from and whats in it?

    Dave Purola,
    N8NTA

  11. #51
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    Al, I'm confused..... Where does RawData[3] come from and whats in it?
    Dave, RawData array will contain the 16 readings you have taken from your system (ADC ; counter; etc.) . Once you apply Miss Melanie's sorting algorithm you will end up with your 16 values ordered in ascending order RawData[0] will contain the smallest reading while RawData[15] will contain the largest one.

    The suggested technique is to discard the first 4 readings and the last 4 readings and average the central 8 reading, in such a way you will not enter into your average calculation anomalous reading (spikes for instance).

    The Boroko issue was that since he is using the 16 bits counter, he was concerned in averaging the 8 raw data in the coventional way, due to the fact that a word will overflow over 65k and he didn't want to use long type variable.

    This method, I have proposed, simply extract the differences from the 8 central values, which can be handled with a single word variable. Once the differences are extracted and summed up into RawData[0] (which is available because its content has been discarded) then you calculate the average shifting the bits with this instruction RawData[0] = RawData[0]>>3

    Now if you add this average to the subtractor used (in our case RawData[3]) all you get is the data average.

    Naturally the code snippet should be called after a call to the sorting routine.

    Hoping to have clear the matter.

    Al.
    All progress began with an idea

  12. #52
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default

    Hi folks,

    Well, another learning moment! For the past week or so, I have been working on the previously mentioned sorting algorithm. I have been peeking in on the forum, but saw Al's name as the last one that replied so I didn't open it. Of course, I missed that there were actually 2 replies and that masked that there had been activity.

    Thanks for the suggestion. I will study it and see how long it takes me to understand it.

    In the mean time, this is where I have been churning. Puzzles me greatly, because it doesn't give anything near what I think it should.
    Code:
    '*          :  18F1330                                          *
    '****************************************************************
    DEFINE OSC 32
    OSCCON  = %11111100          ' INTOSC primary, 8MHz 
    OSCTUNE = %11111111          ' ENABLE 4x PLL = 32mHz
    DEFINE HSER_RCSTA 90h        ' Enable serial port & continuous receive
    DEFINE HSER_TXSTA 24h        ' Enable transmit, BRGH = 1
    DEFINE HSER_CLROERR 1        ' Clear overflow automatically
    DEFINE HSER_SPBRG 138        ' 57600 Baud @ 32MHz, -0.08%
    SPBRGH = 0
    BAUDCON.3 = 1                ' Enable 16 bit baudrate generator
    
    DataA   var WORD
    RawData var WORD [16]           'full program uses 16 and strips top
    DatAvg  var byte                '   and bottom readings
    DatSort var byte                ' 
    DatCnt  var byte                ' count the 16 data entries
    AvgCount con 8                  ' number of readings to average (1/x)
    DatAvg   = 2500                 ' seed number to start averaging
    
    
    RawData[4]= 20000                ' this data represents 8 different
    RawData[5]= 21000                ' readings that come from a TMR0
    RawData[6]= 22000                ' capture that is working.  Fixed 
    RawData[7]= 23000                ' values here for testing
    RawData[8]= 24000
    RawData[9]= 25000
    RawData[10]= 26000
    RawData[11]= 27000
    pause 2000
    '-- Average middle 8 readings ---------------------------------------
    Average:
       for DatSort = 0 to 7                    ' get 8 readings
        Hserout["DA=",#DatAvg,", RD",#DatSort,"=",#RawData[DatSort]]
        DatAvg = DatAvg - (DatAvg/AvgCount)             'subtract 1/x from Avg
        hserout[", 1/x=",#(DatAvg/AvgCount)," DA- = ",#DatAvg]
        DatAvg = DatAvg + (RawData[DatSort]/AvgCount)  'add 1/x of new reading 
        Hserout[", DA+ = ",#DatAvg,13,10] 
         next DatSort
      hserout[13,10]
    '    hserout[", DA ",#DatAvg,13,10]
       goto Average
    Here is a RealTerm screen of the output
    Code:
    DA=219, RD4=20000, 1/x=24 DA- = 192, DA+ = 132                                
    DA=132, RD5=21000, 1/x=14 DA- = 116, DA+ = 181                                
    DA=181, RD6=22000, 1/x=19 DA- = 159, DA+ = 93                                 
    DA=93, RD7=23000, 1/x=10 DA- = 82, DA+ = 141                                  
    DA=141, RD8=24000, 1/x=15 DA- = 124, DA+ = 52                                 
    DA=52, RD9=25000, 1/x=5 DA- = 46, DA+ = 99                                    
    DA=99, RD10=26000, 1/x=10 DA- = 87, DA+ = 9                                   
    DA=9, RD11=27000, 1/x=1 DA- = 8, DA+ = 55
                                                                                                                       
    DA=55, RD4=20000, 1/x=6 DA- = 49, DA+ = 245                                   
    DA=245, RD5=21000, 1/x=26 DA- = 215, DA+ = 24                                 
    DA=24, RD6=22000, 1/x=2 DA- = 21, DA+ = 211                                   
    DA=211, RD7=23000, 1/x=23 DA- = 185, DA+ = 244                                
    DA=244, RD8=24000, 1/x=26 DA- = 214, DA+ = 142                                
    DA=142, RD9=25000, 1/x=15 DA- = 125, DA+ = 178                                
    DA=178, RD10=26000, 1/x=19 DA- = 156, DA+ = 78                                
    DA=78, RD11=27000, 1/x=8 DA- = 69, DA+ = 116
    I can't yet find a pattern or a reason. Maybe its time for a bit of sleep. I will work on it more later.
    Thanks
    Bo

  13. #53
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default I'm impressed!

    Hi Al
    I had the same question as Dave until I mapped it out. Until I put it into Excel, I couldn't understand how that was going to work. Very cool indeed.
    The value in RawData[3] didn't matter, since the values were already sorted, it was lower than RD[4]. All it needed to do was act as a reference for the subtraction and then it was added back in canceling itself. I have no idea how you came up with that, but I'm glad folks like you are willing to teach the rest of us.

    The .xls is zipped if anyone would like to see it.

    Thanks
    Bo
    Attached Files Attached Files

  14. #54
    Join Date
    Feb 2008
    Location
    Michigan, USA
    Posts
    231

    Default

    Error found:

    The output from the code on post #52 didn't make sense because somewhere I had aliased a word variable to a byte. For some reason, they don't work the same....

    Things seem to be going much better now.

    Bo

  15. #55
    Join Date
    Mar 2005
    Location
    Cocoa, Florida
    Posts
    40

    Default Re: Number Sort Algorithm

    Quote Originally Posted by Darrel Taylor View Post
    Thank you, thank you,

    So now that I've proven to myself that it works, ...
    back to the topic ...

    I think that changes Melanie's Sort from Post #4, to ...
    Code:
    	CounterA var Byte
    	RawData var Byte [16]
    	.. ..
    
    		'
    		'	Sort Array
    		'	----------
    SortArray:
    	CounterA=0
    SortLoop:
    	If RawData(CounterA+1) < RawData(CounterA) then
    		RawData(CounterA)     = RawData(CounterA) ^ RawData(CounterA+1)
    		RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)
    		RawData(CounterA)     = RawData(CounterA) ^ RawData(CounterA+1)
    		If CounterA > 0 then CounterA=CounterA-2
    		endif
    	CounterA=CounterA+1
    	If CounterA < 15 then goto SortLoop
    	Return
    Now I've got to wonder if it makes any difference?

    edit: The added array operations would probably even slow it down.
    <br>
    This sort just saved my butt, thank you.
    As the PICs get faster, speed is less of a consideration.

Similar Threads

  1. Dynamic USB Serial Number (PIC18F4550)
    By awmt102 in forum mel PIC BASIC Pro
    Replies: 4
    Last Post: - 16th July 2009, 17:03
  2. Working with the random number generator
    By kwelna in forum mel PIC BASIC
    Replies: 9
    Last Post: - 16th January 2007, 17:50
  3. Random number results
    By bartman in forum mel PIC BASIC
    Replies: 3
    Last Post: - 9th March 2005, 17:39
  4. more random number questions
    By bartman in forum mel PIC BASIC
    Replies: 1
    Last Post: - 14th November 2004, 17:55
  5. Split number into variables
    By psmeets in forum mel PIC BASIC Pro
    Replies: 3
    Last Post: - 7th January 2004, 04:15

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts