Number Sort Algorithm


+ Reply to Thread
Page 1 of 2 12 LastLast
Results 1 to 40 of 55
  1. #1
    T.Jackson's Avatar
    T.Jackson Guest

    Post Number Sort Algorithm

    Number sorting algo that I spat out yesterday can sort 10,000 64 BIT numbers in 15 seconds on a PIII 866MHz. Considering the simplicity of it - this is fast! The code is in Visual Basic but shouldn't be too hard to port to PBP. I don't have time to do it at the moment, anyone up for it? If you feel that you have an even better solution, please post it here.

    Code:
    Private Function Sort_Numbers(ByRef Num_Array)
    
       ' (An easy to get your head around algo)
       
       Dim Compare_A As Long
       Dim Compare_B As Long
       Dim Swap As Long
       Dim Array_Pos As Long
       Dim i As Long
       Dim j As Long
       Dim k As Long
       
       i = UBound(Num_Array)                 ' Size / last index of array
       k = i                                 ' Copy of i used to show progress - indexes sorted thus far
       
       Do Until i = 0                        ' Loop until entire list has been sorted
          Compare_A = Num_Array(i)           ' Load comparison var (starting at bottom of list)
          For j = Array_Pos To i             ' Try to find a bigger num (starting from top of list)
             Compare_B = Num_Array(j)        '
             If Compare_B > Compare_A Then   ' This num bigger?
                Swap = Num_Array(i)          ' Swap them
                Num_Array(i) = Compare_B     '
                Num_Array(j) = Swap
                Array_Pos = j                '
                Exit For                     ' Bail out, but we need to come back (might be an even bigger num)
             End If
          Next
          If j > i Then                      ' Num is in correct pos - nothing bigger exists
             i = i - 1                       ' Move to next index
             Array_Pos = 0
             
             ' Show user how many have been sorted so far (yes this will slow things down marginally)
             Progress = "Sorted " & (k - i) & " numbers"
             DoEvents
          End If
       Loop
       
    End Function

  2. #2
    T.Jackson's Avatar
    T.Jackson Guest

    Default Screen Grab

    As you can see from the screen grab below, it sorted 1,000 numbers in 697mS. This figure starts to badly degrade with more than 1,000.

    <img src="http://www.picbasic.co.uk/forum/attachment.php?attachmentid=1872&stc=1&d=118498310 3">
    Attached Images Attached Images  

  3. #3
    T.Jackson's Avatar
    T.Jackson Guest

    Default One Million Numbers!

    Will it sort a million numbers? - Yes it will. In around an estimated 131.94 hours that is. Divide that figure by bout 10 for a really fast modern PC. Maybe even more for a quad core. Happy sorting!

  4. #4
    Join Date
    Jul 2003
    Posts
    2,358

    Default Sorting Numbers

    Let's swing sorting slightly towards PBP... not quite a million numbers though... can't recall too many PICs with that kind of RAM capability, and with other forms of storage you're then relying on their I/O speed characteristics.

    However, in professional embedded applications, when you take an ADC reading, good practice states that you take more than one and eradicate any anomalies. That way, when your sensor sits at the end of a length of cable, you can eliminate lightning strikes and the odd Redneck trying to weld his pickup truck in near proximity.

    Well, the way I achieve that is to take say 16 ADC readings, sort them in sequential order of value, junk the top and bottom four readings as being 'out-of-range', sum and average the middle eight... this makes ADC readings in industrial applications pretty much bomb-proof...

    Now, whilst there's quite a few tricks and treats within this, here's a simple sort routine for doing just that (when you analyse it, it's pretty similar to your example Trent albeit a little more compact)... The Data to be sorted sits in an array called RawData, and when it falls out of the subroutine, RawData is in sequential order. Change DataA and RawData variables to WORDS if you need them. Those that know will notice that the additional variable DataA is only needed because PBP's SWAP command doesn't work with arrays.

    Code:
        CounterA var Byte
        DataA var Byte
        RawData var Byte [16]
        .. ..
    
            '
            '    Sort Array
            '    ----------
    SortArray:
        CounterA=0
    SortLoop:
        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
        Return
    Last edited by ScaleRobotics; - 2nd July 2010 at 17:35.

  5. #5
    T.Jackson's Avatar
    T.Jackson Guest

    Default

    RawData(CounterA+1+0)=DataA
    + 0 ?

    *Like the multiple sample theory - something I never really thought about. But then again, I'm not an engineer.

  6. #6
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    Yes, +0, other than Bruce, Darrel (and perhaps Mister_E), who on this forum knows why?

  7. #7
    T.Jackson's Avatar
    T.Jackson Guest

    Default

    I normally have the ability to at least come up with some sort of opinion with most things (often it's wrong), but on that, I can't even think of one guess, not even an obviously far-fetched one.

  8. #8
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    Going back to the early days of PBP, before Microcode studio, to the days when you carved your code into slate tablets, there was an anomaly/bug with PBP sometimes handling math within array parenthesis. The workaround was to simply add a dummy argument (which goes to show how old that code is). Now I can't remember at which point the error was eradicated without compiling a bunch of test samples across more than half-a-dozen versions of PBP. The code I posted above pretty much works with all versions, though if absolute speed is your thing, you can probably lose the +0 if your PBP is relatively up-to-date.

  9. #9
    T.Jackson's Avatar
    T.Jackson Guest

    Post

    Oh! - well that puts my mind at ease, it's things like that keep me from getting a good nights sleep. I'll be able to switch off tonight and get some rest.

  10. #10
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    Quote Originally Posted by Melanie View Post
    ...Those that know will notice that the additional variable DataA is only needed because PBP's SWAP command doesn't work with arrays.
    Well, there is a way to swap two variables without the need of a third dummy one:

    a=a^b
    b=a^b
    a=a^b

    If you test it with binary numbers be surprised that finally there is swap without dummy!

    Ioannis

  11. #11
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Thumbs up

    Cool.

    And I suppose if someone wanted to test the "Surprise", they might do something like this ...

    Code:
    ;Initialize your hardware first
    
    A      VAR WORD
    B      VAR WORD
    TempA  VAR WORD
    TempB  VAR WORD
    
    LCDOUT $FE,1
    
    For A = 0 to 65535
        LCDOUT $FE,2,"A=",DEC A
        For B = 0 to 65535
            TempA = A
            TempB = B
            TempA = TempA ^ TempB
            TempB = TempA ^ TempB
            TempA = TempA ^ TempB
            IF (TempA <> B) OR (TempB <> A) THEN ; Test Failed
                LCDOUT $FE,1,"Test Failed",$FE,$C0,"A=",DEC A,", B =",DEC B
                STOP
            ENDIF
        Next B
    Next A
    
    LCDOUT $FE,1,"Test Passed!"
    STOP
    Then some 40 hours later (@ 20Mhz) [that's over 4 billion combinations],
    you would no doubt see the message "Test Passed!" on the LCD.

    Only a half hour into it, but it's still passing. Kinda obvious what the result will be.

    Update: 43hrs, Test Passed! (obviously)
    <br>
    Last edited by Darrel Taylor; - 27th July 2007 at 08:26. Reason: Final result
    DT

  12. #12
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    Nice routine Darrel! 40 hours to wait for "Test Passed!", wow!

    Ioannis

  13. #13
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Default

    LOL,

    I think I'll need those 40 hrs. just to wrap my head around why it works.

    It does work, but the explanation eludes me.

    @ Don't tell me, I've still got 38 hrs to go
    <br>
    DT

  14. #14
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Default

    Programs still running, but I think I got the XOR thing figured out.
    Not that I could explain it though.

    Practicing my Flash at the same time

    .. Flash moved down ..
    DT

  15. #15
    Join Date
    Jul 2003
    Posts
    2,405

    Default

    How this logic works is pretty cool. I saw this on the PIClist a few years back.

    Here's how it works.

    a VAR BYTE
    b VAR BYTE
    a = %11001100
    b = %00110011

    a=a^b ' a now = %11001100 ^ %00110011 which = %11111111

    1 ^ 0 = 1. 1 ^ 1 = 0. 0 ^ 0 = 0.

    b=a^b ' b now = %11111111 ^ %00110011 which = %11001100 (value of original a)

    b now contains the original value of a.

    a=a^b ' a now = $11111111 ^ %11001100 which = %00110011 (value of orignal b)

    Now that b = the original value held in a, ^-oring a with b returns the orignal
    value of b, in a.

    Using any two values, it still works the same. Like this;

    a = %11011100
    b = %00110011

    a=a^b ' a now = %11011100 ^ %00110011 which = %11101111
    b=a^b ' b now = %11101111 ^ %00110011 which = %11011100 (value of original a)
    a=a^b ' a now = $11101111 ^ %11011100 which = %00110011 (value of orignal b)

    Pretty nifty way of swapping variables.
    Last edited by Bruce; - 25th July 2007 at 22:16.
    Regards,

    -Bruce
    tech at rentron.com
    http://www.rentron.com

  16. #16
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    And is as fast as using swap technique!

    I was wondering where I first read about it and after alot of searching, it was on a summer double Elektor issue.

    Ioannis

  17. #17
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Lightbulb

    Ioannis,

    Thanks for the interesting idea to ponder.

    And thanks for the extra examples Bruce. But while it does show that it gets from A to B and visa versa, it didn't really answer the Why? that had me so baffeled. When I get baffeled I usually become obsessed at figuring out the why, especially when it seems like it should be so simple (Like 3 XOR's in a row).

    My biggest problem was thinking it was combining the bits with the first A=A^B, then somehow pulling the bits back out with the next XOR. But none of that was making any sense.

    After making the Flash, I realized that the XOR gate should really be called the "They're Different" gate, which is what the XOR does. If both inputs are the same the output is 0, if they're different, the output is 1.

    Then it all made perfect sense.

    The first A = A^B determines if both bits are Different or not, and stores it back in A.

    Since you still know the original B value, and you know if the 2 are different then ...

    If B = 1 and "They are Different" then A used to be = 0, which accounts for the B = A^B

    The last A = A^B does the same thing. If they are different, and you know the new B is a 0, then the new A has to be a 1.

    <OBJECT CLASSID= "clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" WIDTH="600" HEIGHT="300" CODEBASE="http://active.macromedia.com/flash5/cabs/swflash.cab#version=5,0,0,0"><PARAM NAME="MOVIE" VALUE="http://www.pbpgroup.com/files/XOR.swf"><PARAM NAME="PLAY" VALUE="true"><PARAM NAME="LOOP" VALUE="true"><PARAM NAME="WMODE" VALUE="opaque"><PARAM NAME="QUALITY" VALUE="high"><EMBED SRC="http://www.pbpgroup.com/files/XOR.swf" WIDTH="600" HEIGHT="300" PLAY="true" LOOP="true" WMODE="opaque" QUALITY="high" PLUGINSPAGE="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash"></EMBED></OBJECT>

    I feel better now.
    <br>
    DT

  18. #18
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    Cool Darrel!

    But what is buzzing me more, is how one can think about it in the first place. He/she must be really clever one. So simple, so clever!

    Ioannis
    Last edited by Ioannis; - 13th May 2015 at 08:51.

  19. #19
    Join Date
    Jul 2003
    Posts
    2,405

    Default

    I've found a few nifty tricks like this on the Microchip forum in the Tips &
    Tricks section http://forum.microchip.com/tm.aspx?m=165770

    Really gets one to thinking.

    The PIClist is another good resource, but the signal-to-noise ratio there can
    be pretty high.

    Nice job on the Flash XOR gate Darrel...;o}
    Regards,

    -Bruce
    tech at rentron.com
    http://www.rentron.com

  20. #20
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Default

    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>
    Last edited by Darrel Taylor; - 26th July 2007 at 14:07. Reason: .
    DT

  21. #21
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    The one thing for sure is that code will use one variable less.

    As for speed, I don't know. Operation either on swap or with the XOR thing i believe are the same...

    Ioannis

  22. #22
    T.Jackson's Avatar
    T.Jackson Guest

    Post

    You know, if you say Super-cala-fragile-listic-expealidoius, backwards, at exactly 3:03 am, the Blair Witch will appear before you and grant you with exactly one wish. Be careful what you wish for though.

  23. #23
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    Quote Originally Posted by T.Jackson View Post
    You know, if you say Super-cala-fragile-listic-expealidoius, backwards, at exactly 3:03 am, the Blair Witch will appear before you and grant you with exactly one wish. Be careful what you wish for though.
    Didn't that was said by Mary Poppins? Iliked it a lot!

    But how does this connect with the above? Sorry I cannot understand, as english is second language to me.

    Ioannis

  24. #24
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    It doesn't work (because Trent forgot to use his spellchecker)... I'm worried about the 'fragile' section in the middle of the word...

  25. #25
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    and needs an 'c' in expealidoius like: expealidocius

    Ioannis

  26. #26
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Talking

    The biggest problem is that it takes longer than a second to say it.

    There's no way to say the whole thing at exactly 3:03 am.

    But backwards (according to the movie) would be.
    dociousaliexpiisticfragilcalirupus

    docious-ali-expi-istic-fragil-cali-rupus
    <br>
    DT

  27. #27
    T.Jackson's Avatar
    T.Jackson Guest

    Default

    Legend has it that if you stand in front of a mirror, any time past midnight, and say three times; "I don't believe in the Bell Witch" - the next morning you will wakeup with finger nail scratches on your cheek.

  28. #28
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959

    Default

    Do you have any more of those pills?

    And, can I have some??
    <br>
    DT

  29. #29
    T.Jackson's Avatar
    T.Jackson Guest

    Default

    That legend is for real Darrel.

  30. #30
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    > next morning you will wakeup with finger nail scratches on your cheek.

    ... and there I was wondering why I never get dated more than once!

  31. #31
    Join Date
    Sep 2009
    Posts
    19

    Default how does it work?

    Hello.
    I apologize for reviving old thread but forum is already crowded with so many topics I don't want to aggrandize it further.

    In mrs. Melanie's routine I don't understand the following:
    Code:
    SortArray:
       ...
       IF CounterA>0 then CounterA=CounterA-2
       ...
       CounterA=CounterA+1
    IF CounterA<15 THEN SortArray
    As I see it, after the first pass through the loop CounterA is 1, so when it hits IF CounterA>0... wouldn't that make CounterA bigger than15 and exit the loop (CounterA war byte so 1-2=255)?
    Can someone please explain it to me?

  32. #32
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    >Mrs Melanie!

    Don't marry me off yet - I'm having way too much fun being single!

    This is a SWAP SORT routine with an Array of 16 elements... (this version is in ASCENDING order, ie the smallest value will end up in RawData(0) and the largest value will end up RawData(15).

    First time through the loop CounterA=0 (not 1 as you stated).

    You compare RawData(1) with RawData(0) and if RawData(1) is smaller you swap them (NOT if it's bigger or if is the same).

    There was an ARRAY BUG in PBP V2.42, which caused problems with Array manipulation - for example RawData(CounterA+1), the workaround (before MeLabs fixed it) was to add a dummy proceedure, so this became RawData(CounterA+1+0). This BUG has long been fixed, so you don't actually need the +0 bit nowadays.

    Only if you are NOT at the start of the Array Sort (ie CounterA>0) do you then go back and look at the previous set of Array elements and compare those again (because you've just swapped the upper one of them). You actually subtract 2, because the very next step adds one, so in essence you only go back one Array step. If you are already at the beginning of the Array (ie CounterA=0), you DON'T step back, because that will cause you to step outside your array limits, so you move forward by adding 1 to CounterA.

    You repeat the process until you've scanned the whole array and CounterA=15 (your upper Array limit).

    So... back to your question...

    Whether you SWAP or NOT, if CounterA=0 then the -2 will never happen, you can only move FORWARDS to CounterA=1 (ie CounterA=CounterA+1).

    If CounterA=1, then if you DON'T Swap, you move FORWARDS (as above), but if you DO SWAP then CounterA will move BACK by ONE Count (ie CounterA=-2+1), which if CounterA was 1 to start with, it will now move back to be Zero.

  33. #33
    Join Date
    Sep 2009
    Posts
    19

    Default

    Don't marry me off yet - I'm having way too much fun being single!
    Please accept my apology, English is not my native language so I make many mistakes.


    Thank you very much for your kind and patient response. Now I see how stupid my question really was. I grasped on CounterA+1 & CounterA-2 as a bull on red flag therefore completely dropping the rest out of my sight. I'll put more effort next time instead of bothering with a silliness.
    Thanks again for the explanation, as well for sharing the routine.

    Kind regards

  34. #34
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    *smiles* No appologies are required!

    Doesn't matter about asking questions - that is what this forum is here for, everyone who reads learns something from them.

  35. #35
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    Well, the way I achieve that is to take say 16 ADC readings, sort them in sequential order of value, junk the top and bottom four readings as being 'out-of-range', sum and average the middle eight... this makes ADC readings in industrial applications pretty much bomb-proof...
    Miss Melanie, in doing so you are potentially junking good data, but you can also potentially retain and use in your mean bad data, since you have no way to know how many bad readings you will take with your sampling.

    A statistically correct approch should be to calculate the mean and the standard deviation (sd), of all your 16 readings, than retain all data within +/- 1 or 2 sd depending esclusively on your need.

    A simpler approach could be to decide which threshold (in percentage of the mean) to apply to reduce the variance, than take the mean of all the 16 readings and discard all the data beyond the threshold limit.

    In both cases you will not need to sort your array.

    Al.
    Last edited by aratti; - 8th November 2009 at 17:53.
    All progress began with an idea

  36. #36
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    But the maths to do those calculations I feel are more code hungry than just sorting...

    Ioannis

  37. #37
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    Ioannis, if the number that you will display has no importance then you can fix it with a constant, display will be rock stable (always the same number). On the other hand, if the number should provide you usefull information then you must treat it in such a way to preserve those information, which means you must use the correct statistical approch, regardless how code hungry the algorithm could be.

    Al.
    Last edited by aratti; - 9th November 2009 at 09:47.
    All progress began with an idea

  38. #38
    Join Date
    Nov 2003
    Location
    Greece
    Posts
    3,125

    Default

    Of course I agree with you Al.

    I just feel that Melanies approach is faster giving almost same result for most cases.

    Sure if you need the most precise results, one in the way to follow.

    Ioannis

  39. #39
    Join Date
    Jul 2003
    Posts
    2,358

    Default

    There are many ways of accomplishing the same task. Give that task to a dozen engineers, you may get a dozen different approaches, each achieving the desired result, and each achieving that result with different methodology. Really, in electronics and programming there is no SINGLE correct way of doing anything and the methodology you employ rests with your imagination which makes our business just as exciting and creative as any Artist painting a canvas.

    If I am measuring ambient temperature for example, I don't expect to take sixteen readings 50uS apart and discover twelve of them to measure around +22.7 Celcius, one to measure -20, one measures -40 Celcius, one measures +400 and one measures +700 Celcius. But that is exactly the kind of result you might get is you experience a local lightning strike with spikes being induced into your electronics. Very short bursts of total rubbish.

    Now using a conventional method of summation would produce an erroneous result, but the temperature may well drop to -20 or minus 40 in winter, so that could also be technically valid data, but in the case above, we know that the onset of winter doesn't happen in 100uS, so we need to trash the data at the extreemes (even if it might be good data).

    Now in the code I published some years back, I put forward an idea of taking multiple samples, sorting them, discarding those results at the fringes and concentrating only on the centre median of our collection of data. This works good in the majority of industrial and environmental applications and even for motion control on an industrial assembly robot (filtering localised welding spikes). The amount of data you discard is not arbitrary, it depends on the number of samples you've taken and the TIME you've sampled them across. I know lightning tends to be short duration spikes, so out of a milliseconds worth of sampling, I know that anything out of the ordinary lasting 50 or 100uS we can happilly junk. But, if I was creating the firmware for a new Digital Oscilloscope or sampling an Audio waveform for an Amplifier, this would obviously not be the correct approach.

  40. #40
    Join Date
    May 2008
    Location
    Italy
    Posts
    825

    Default

    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.
    Last edited by aratti; - 19th December 2009 at 18:14.
    All progress began with an idea

Similar Threads

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