Number Sort Algorithm


+ Reply to Thread
Results 1 to 40 of 55

Hybrid View

  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
    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

  8. #8
    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

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