Proton BASIC Community

Hi All

Is there a fast efficient sorting algo so I can get and average max and min number based on the current 10 max/min values

Basically a 10 (or more) element array that you compare numbers against. If its say bigger than element 7 (smaller than 8 ) in the array you shift the other down and insert the new number losing the smallest.

I'm not looking for the code to be written just describe a fast efficient way of doing it

Any hints appreciated

Tim
   

I've always found the most effective and safe mechanism for that is a bubble sort. Especially when there are a small amount of elements to sort.

You can include the "Median_Filters.inc" file into your program and take a look at the mechanism used for median fitering procedures. i.e. The middle value.

For min and max values, just take the first and last of the sorted array's elements. However, make sure you choose the sort for the correct variable size, otherwise, if too small it will not give the correct results, and if too large, it will waste RAM, code memory, and speed.

For example, if looking for unsigned 16-bit min and max values, you can use:

'
'   /\\\\\\\\\
'  /\\\///////\\\
'  \/\\\     \/\\\                                                 /\\\          /\\\
'   \/\\\\\\\\\\\/        /\\\\\     /\\\\\\\\\\     /\\\\\\\\   /\\\\\\\\\\\  /\\\\\\\\\\\  /\\\\\\\\\
'    \/\\\//////\\\      /\\\///\\\  \/\\\//////    /\\\/////\\\ \////\\\////  \////\\\////  \////////\\\
'     \/\\\    \//\\\    /\\\  \//\\\ \/\\\\\\\\\\  /\\\\\\\\\\\     \/\\\         \/\\\        /\\\\\\\\\\
'      \/\\\     \//\\\  \//\\\  /\\\  \////////\\\ \//\\///////      \/\\\ /\\     \/\\\ /\\   /\\\/////\\\
'       \/\\\      \//\\\  \///\\\\\/    /\\\\\\\\\\  \//\\\\\\\\\\    \//\\\\\      \//\\\\\   \//\\\\\\\\/\\
'        \///        \///     \/////     \//////////    \//////////      \/////        \/////     \////////\//
'                                  Let's find out together what makes a PIC Tick!
'
' Use a bubble sort mechanism to extract the smallest, middle, and largest values from an array.
' Written for the Positron8 compiler by Les Johnson.
'
    Device = 18F25K20                           ' Tell the compiler what device to compile for
    Declare Xtal = 16                           ' Tell the compiler what frequency the device will be operating at (in MHz)
'
' Setup HRSout
'
    Declare Hserial_Baud = 9600                   ' Set the Baud rate to 9600
    Declare HRSOut_Pin  = PORTC.6                ' Set the TX pin
'
' Create global variables here
'
    Dim My_WordArray[10] As Word Heap = 40, 600, 300, 800, 1000, 2, 10, 9000, 200, 32000 ' Create a word array with jumbled values for the demo
    Dim wMiddle_Value As Word

'----------------------------------------------------------------------------
' The main program starts here
'
Main:
    wMiddle_Value = Sort16(My_WordArray, SizeOf(My_WordArray))

    HRsoutLn "Min    = ", Dec wMin_Value
    HRsoutLn "Max    = ", Dec wMax_Value
    HRsoutLn "Middle = ", Dec wMiddle_Value

'--------------------------------------------------------
' An unsigned 16-bit bubble sort filter procedure that uses indirect access to the array passed to it
' Input     : pArrayAddr holds the address of the array to sort
'           : pArraySize holds the size of the array to sort (3 to 255)
' Output    : Sorts the array passed to it
'           : Returns the median value from the array (middle value)
'           : Global variable wMin_Value holds the minimum value from the array
'           : Global variable wMax_Value holds the maximum value from the array
' Notes     : None
'
Proc Sort16(ByRef pArrayAddr As Word, pArraySize As Byte), Word
Global Dim wMin_Value As Word                                   ' Holds the smallest value from the sorted array
Global Dim wMax_Value As Word                                   ' Holds the largest value from the sorted array
    Dim tSwap_Occured As Bit                                    ' Indicates if the sort is complete
    Dim bElementCount As Byte                                   ' Holds a count of the size of the
    Dim wElement_0    As Word                                   ' Holds the value of an element within the array
    Dim wElement_1    As Word                                   ' Holds the value of an element + 1 within the array
    Dim wArrayAddress As Word = pArrayAddr                      ' Place the start address of the array into a working variable

    Repeat
        wArrayAddress = pArrayAddr                              ' Place the start address of the array into wArrayAddress
        tSwap_Occured = 0                                       ' Clear the flag that indicates a swap occured
        bElementCount = 1                                       ' Reset the array element counter
        Repeat                                                  ' Loop for each cell of the array...
            wElement_0 = Ptr16(wArrayAddress++)                 ' Extract an element from the array then increment the address
            wElement_1 = Ptr16(wArrayAddress--)                 ' Extract an element from the array then decrement the address
            If wElement_0 > wElement_1 Then                     ' Is the contents of element + 0 greater than the contents of element + 1?
                Ptr16(wArrayAddress++) = wElement_1             ' Yes. So store the element + 1 into element + 0 then increment the address
                Ptr16(wArrayAddress) = wElement_0               ' Store element + 0 into element + 1
                tSwap_Occured = 1                               ' Set the flag if a swap occurred
            Else                                                ' Otherwise....
                wArrayAddress = wArrayAddress + 2               ' Increment the array address to examine the next element pair
            EndIf
            Inc bElementCount                                   ' Check the next element of the array
        Until bElementCount = pArraySize                        ' Until the end of the array is reached
    Until tSwap_Occured = 0                                     ' Keep sorting until no more swaps occur
    wMin_Value = Ptr16(pArrayAddr)                              ' Get the first element of the sorted array
    wMax_Value = Ptr16(wArrayAddress)                           ' Get the last element of the sorted array
    pArraySize = pArraySize / 2                                 ' \
    pArraySize = pArraySize * 2                                 ' | Calculate the address of the middle element within the array
    wArrayAddress = pArrayAddr + pArraySize                     ' /
    Result = Ptr16(wArrayAddress)                               ' Return the value from the middle address of the array
EndProc

Which is a slightly altered Median16 procedure, and on the serial terminal, it will display:

Min    = 2
Max    = 32000
Middle = 600

With 2 being the smallest value in the array's elements, 32000 being the largest value, and 600 being the middle (median) value.

Thanks Les

I did think of the bubble sort but the issue is that the data needs to be constantly updated and the max min is not balanced eg there will be a min for 99% of the time so just adding to the array and sorting it will just end up with an array of lows


Tim

With the Sort16 procedure, the array passed to it gets sorted, so adding a new value to array's element 0, then running the Sort16 procedure again, will continuously sort it and give the min, middle and max values per addition to it.

Something like:

'
' Create global variables here
'
    Dim My_WordArray[10] As Word Heap
    Dim wSampleValue As Word

'----------------------------------------------------------------------------
' The main program starts here
'
Main:
    Seed $0345
    Clear My_WordArray
    Do
        wSampleValue = Random
        My_WordArray[0] = wSampleValue
        Sort16(My_WordArray, SizeOf(My_WordArray))
        HRsoutLn "For Sample: ", Dec wSampleValue, ": Min = ", Dec wMin_Value, ": Max = ", Dec wMax_Value
        DelayMs 200
    Loop

And on the serial terminal it will show:

For Sample: 1674: Min = 0: Max = 1674
For Sample: 3349: Min = 0: Max = 3349
For Sample: 6698: Min = 0: Max = 6698
For Sample: 13396: Min = 0: Max = 13396
For Sample: 26793: Min = 0: Max = 26793
For Sample: 53586: Min = 0: Max = 53586
For Sample: 41637: Min = 0: Max = 53586
For Sample: 17739: Min = 0: Max = 53586
For Sample: 35478: Min = 0: Max = 53586
For Sample: 5421: Min = 1674: Max = 53586
For Sample: 10842: Min = 3349: Max = 53586
For Sample: 21685: Min = 5421: Max = 53586
For Sample: 43370: Min = 6698: Max = 53586
For Sample: 21204: Min = 10842: Max = 53586
For Sample: 42408: Min = 13396: Max = 53586
For Sample: 19280: Min = 17739: Max = 53586
For Sample: 38561: Min = 19280: Max = 53586
For Sample: 11586: Min = 11586: Max = 53586
For Sample: 23172: Min = 21204: Max = 53586
For Sample: 46344: Min = 21685: Max = 53586
For Sample: 27153: Min = 23172: Max = 53586
For Sample: 54307: Min = 26793: Max = 54307
For Sample: 43079: Min = 27153: Max = 54307
For Sample: 20623: Min = 20623: Max = 54307
For Sample: 41247: Min = 35478: Max = 54307
For Sample: 16958: Min = 16958: Max = 54307
For Sample: 33916: Min = 33916: Max = 54307
For Sample: 2296: Min = 2296: Max = 54307
For Sample: 4593: Min = 4593: Max = 54307
For Sample: 9187: Min = 9187: Max = 54307
For Sample: 18374: Min = 18374: Max = 54307
For Sample: 36749: Min = 36749: Max = 54307
For Sample: 7962: Min = 7962: Max = 54307
For Sample: 15924: Min = 15924: Max = 54307
For Sample: 31849: Min = 31849: Max = 54307
For Sample: 63699: Min = 38561: Max = 63699
For Sample: 61863: Min = 41247: Max = 63699
For Sample: 58191: Min = 41637: Max = 63699
For Sample: 50847: Min = 42408: Max = 63699
For Sample: 36159: Min = 36159: Max = 63699
For Sample: 6782: Min = 6782: Max = 63699
For Sample: 13564: Min = 13564: Max = 63699
For Sample: 27128: Min = 27128: Max = 63699
For Sample: 54256: Min = 43079: Max = 63699
For Sample: 42977: Min = 42977: Max = 63699
For Sample: 20419: Min = 20419: Max = 63699
For Sample: 40839: Min = 40839: Max = 63699
For Sample: 16142: Min = 16142: Max = 63699
For Sample: 32284: Min = 32284: Max = 63699
For Sample: 64569: Min = 43370: Max = 64569
For Sample: 63602: Min = 46344: Max = 64569
For Sample: 61669: Min = 50847: Max = 64569
For Sample: 57803: Min = 53586: Max = 64569
For Sample: 50071: Min = 50071: Max = 64569
For Sample: 34606: Min = 34606: Max = 64569
For Sample: 3676: Min = 3676: Max = 64569
For Sample: 7353: Min = 7353: Max = 64569
For Sample: 14706: Min = 14706: Max = 64569
For Sample: 29413: Min = 29413: Max = 64569
For Sample: 58826: Min = 54256: Max = 64569
For Sample: 52117: Min = 52117: Max = 64569
For Sample: 38698: Min = 38698: Max = 64569
For Sample: 11861: Min = 11861: Max = 64569
For Sample: 23722: Min = 23722: Max = 64569
For Sample: 47445: Min = 47445: Max = 64569

Which are the continuous min and max values of the new sample value added to the array.

And to not remove the previous lowest value, the new sample can be placed in the 'middle' element of the array, then sorted continuously, so unless a new lower value is seen, the original low and high values will remain. Something like:

Main:
    Seed $0345
'
' Pre-Load the array with samples before continuous sorting them
'
    For bIndex = 0 To Bound(My_WordArray)
        wSampleValue = Random                         ' Get a sample value
        My_WordArray[bIndex] = wSampleValue
    Next

    Do
        wSampleValue = Random                         ' Get a sample value
        My_WordArray[5] = wSampleValue                ' Place it in the middle of the array
        Sort16(My_WordArray, SizeOf(My_WordArray))    ' Sort the array lowest to highest values
        HRsoutLn "For Sample: ", Dec wSampleValue, ": Min = ", Dec wMin_Value, ": Max = ", Dec wMax_Value
        DelayMs 200
    Loop

Before any continuous sorting can be done, the sorting array needs to be first pre-loaded with values.

So you will need to pre-load the array with samples before the sorting occurs, otherwise, a value less that 0 is required to knock off the lowest value if the array is first cleared, and that will not happen with unsigned integer values.

Wow Les

I was still hacking together a routine. Yours is way better (more complex but way better)

I will give it a good test

Tim

If it is only the min and max values required, you can remove the median extraction part of the Sort16 procedure, as below:

'--------------------------------------------------------
' An unsigned 16-bit bubble sort filter procedure that uses indirect access to the array passed to it
' Input     : pArrayAddr holds the address of the array to sort
'           : pArraySize holds the size of the array to sort (3 to 255)
' Output    : Global variable "wMin_Value" holds the minimum value from the array
'           : Global variable "wMax_Value" holds the maximum value from the array
' Notes     : Sorts the array passed to it
'
Proc Sort16(ByRef pArrayAddr As Word, pArraySize As Byte)
Global Dim wMin_Value As Word                                   ' Holds the smallest value from the sorted array
Global Dim wMax_Value As Word                                   ' Holds the largest value from the sorted array
    Dim tSwap_Occured As Bit                                    ' Indicates if the sort is complete
    Dim bElementCount As Byte                                   ' Holds a count of the size of the array
    Dim wElement_0    As Word                                   ' Holds the value of an element within the array
    Dim wElement_1    As Word                                   ' Holds the value of an element + 1 within the array
    Dim wArrayAddress As Word = pArrayAddr                      ' Place the start address of the array into a working variable

    Repeat
        wArrayAddress = pArrayAddr                              ' Place the start address of the array into wArrayAddress
        tSwap_Occured = 0                                       ' Clear the flag that indicates a swap occured
        bElementCount = 1                                       ' Reset the array element counter
        Repeat                                                  ' Loop for each cell of the array...
            wElement_0 = Ptr16(wArrayAddress++)                 ' Extract an element from the array then increment the address
            wElement_1 = Ptr16(wArrayAddress--)                 ' Extract an element from the array then decrement the address
            If wElement_0 > wElement_1 Then                     ' Is the contents of element + 0 greater than the contents of element + 1?
                Ptr16(wArrayAddress++) = wElement_1             ' Yes. So store the element + 1 into element + 0 then increment the address
                Ptr16(wArrayAddress) = wElement_0               ' Store element + 0 into element + 1
                tSwap_Occured = 1                               ' Set the flag if a swap occurred
            Else                                                ' Otherwise....
                wArrayAddress = wArrayAddress + 2               ' Increment the array address to examine the next element pair
            EndIf
            Inc bElementCount                                   ' Check the next element of the array
        Until bElementCount = pArraySize                        ' Until the end of the array is reached
    Until tSwap_Occured = 0                                     ' Keep sorting until no more swaps occur
    wMin_Value = Ptr16(pArrayAddr)                              ' Get the first element of the sorted array (minimum value)
    wMax_Value = Ptr16(wArrayAddress)                           ' Get the last element of the sorted array (maximum value)
EndProc

It will then only load the global variables: wMin_Value and wMax_Value, and sort the array passed to it, and it makes it a bit smaller and faster to operate.

Are they 8-bit or 16-bit elements to sort in your program? For an 8-bit array, the sort procedure can be made smaller and faster.

For reference below is the signal I need to detect the transition change eg know when the level is high and low. I'm using a built in 10bit ADC so all values are 16bit

The issue is that the signal while it will look the same will change in amplitude and its base voltage.

I need to record the max and min values. As I said before the duty will be 99% one voltage so I need to update the max and min continually as on start up I have to wait for a transition to get the max and min values. Then I can start detecting the status of the signal. In realty I will need to reset and get it to refresh its max and min as it may drift.

The idea is just so I can get a middle to do a basic if  x > threshold then ..

Do you just need to detect the transition or the physical delta? Am thinking you could use a comparator on the PIC with the signal feeding both inputs via resistors but one input has a capacitor to delay the transition change and hence creates a logic pulse or interrupt.

Or even simpler, drive the signal through a capacitor into a logic amplifier (basically non buffered logic gate with a 1M resistor from ouput to input). The resistor holds the gate at the transition point and makes a extremely fast high gain amplifier. These have huge open loop gain, thus will saturate on the transitions and then it's VCC/VSS.

If it's min max then you could use active peak detectors with the logic amp as a trigger pulse to drive an interrupt which then measures the peak detector outputs via ADC. Maybe look at the ZCD peripheral is there is one.

JohW

I have in the past used a comparator but it suffers from a serious issue in that you have to calibrate it. I had a system to calibrate on the fly and save the current setting to Eeprom. However if the signal changed while off eg what the sensor saw got dirty then it failed.

I have to watch the signals and decide at start up the values and periodically adjust the threshold.

Another person has done testing and found that large data arrays (eg 10 elements) are a kind of waste of time and just uses now simple single max min values.

I fear I have been over thinking this. I will revert to say 2 or 3 hard coded max mins and not arrays

Tim

For that type of min/max sorting, you can try the procedure below. It also has a small demo as the main program:

'----------------------------------------------------------------------------
' The main program starts here
'
Main:
    Seed $0135

    Sort_HiLo16(0, 1)                                       ' Reset the internal variables of Sort_HiLo16 before commencing sorting
    Do                                                      ' Create a loop
        wSampleValue = ((Random) // 1000) + 1               ' Create a random number between 1 and 999
        Sort_HiLo16(wSampleValue, 0)                        ' Sort the value as higher or lower then the previous value sent to it
        HRsoutLn "For Sample: ", Dec wSampleValue,          ' \
                 " | Min = ", Dec wMin_Value,               ' | Display the values on a serial terminal
                 " | Max = ", Dec wMax_Value                ' /
        DelayMs 100                                         ' A small delay between sampling and sorting
    Loop                                                    ' Do it forever

'----------------------------------------------------------------------------
' Sort the highest a lowest values from a sequence of values sent
' Input     : pValue holds the value to sort into high or low
'           : pReset is 1 to reset the internal sorting variables, 0 for the sort to occur
' Output    : Global variable wMin_Value holds the minimum value from the array
'           : Global variable wMax_Value holds the maximum value from the array
' Notes     : None
'
Proc Sort_HiLo16(pValue As Word, pReset As Bit)
Global Dim wMin_Value As Word                               ' Global variable to hold the smallest value
Global Dim wMax_Value As Word                               ' Global variable to hold the largest value
    Dim wPrevMin As Word                                    ' Holds the previous smallest value
    Dim wPrevMax As Word                                    ' Holds the previous largest value

    If pReset = 1 Then                                      ' Is pReset 1?
        wPrevMin = 65535                                    ' \
        wPrevMax = 0                                        ' | Yes. So reset the sorting variables
        wMin_Value = 0                                      ' |
        wMax_Value = 0                                      ' /
    Else                                                    ' Otherwise... pReset is 0...
        If pValue < wPrevMin Then                           ' So... Is pValue less that the previous small value?
            wMin_Value = pValue                             ' Yes. So load wMin_Value with the contents of pValue
            wPrevMin = pValue                               ' Make a copy of the value

        ElseIf pValue > wPrevMax Then                       ' Is pValue greater that the previous largest value?
            wMax_Value = pValue                             ' Yes. So load wMax_Value with the contents of pValue
            wPrevMax = pValue                               ' Make a copy of the value
        EndIf
    EndIf
EndProc

After two calls to the Sort_HiLo16 procedure, it will produce continuous valid highest and lowest values, and its internal variables can be reset via a parameter, for fresh samples to be sent to it for sorting.

Quote from: TimB on Jun 11, 2024, 05:36 AM... I fear I have been over thinking this. I will revert to say 2 or 3 hard coded max mins and not arrays

My thoughts, if I have understood your requirement correctly.

If you fed your 'square wave like waveform' into a simple RC differentiator circuit (dv/dt) then your output would be large during rapid waveform change - i.e. the main transition and low during steady state i.e. the steady low or high periods. The dv/dt would be quite easy to implement in software by taking regular readings and comparing each reading with the predecessor. When the difference fell below a certain value then you have detected a steady state.

John

John

Its not a regular square wave it has a duty of 99.9% low and 0.1% high and as in the image above the signal has peaks outside the average for the state. Also the high may last only 500ms. It has to analyse the signal and output it as a TTL high low signal

There is another issue in that the signal will change in amplitude and base voltage.

I have written a simple 4 min and 4 max value peak and low detector. Once it sees one peak it can work out the mid point and sets that as the threshold. It then runs OK.

However if say the real mid point goes higher then it will not detect the new min values as the stored mins are lower.

I have added to the code to get an average when it notes a transition and using a timer after a short period will check the average against the max or min and if need be change the max min values to force a re-calc of the effected value

This way as long as the signal does not drift quickly to make the threshold be wrong it is self correcting.

If the amplitude also changes, there will be no min and max, because there will not be a default stable state to try and match for the next sample.

You may need to use a constant amplitude circuit to normalise the signal before it is analysed, so the ADC or a peak detector has a constant amplitude to work with.

Quote from: TimB on Jun 11, 2024, 09:41 PMIts not a regular square wave it has a duty of 99.9% low and 0.1% high and as in the image above the signal has peaks outside the average for the state. Also the high may last only 500ms. It has to analyse the signal and output it as a TTL high low signal

There is another issue in that the signal will change in amplitude and base voltage.

Hi Tim,
sorry I misunderstood, but can you post a more realistic oscillogram of the waveform over a longer period?

Thanks Les

That would be the way to go.

For more info the sensor is a bubble sensor eg a slot opto with a silicone tube through the slot that water passes through with occasional bubbles. 99% of the time its water and hence produces an attenuated signal as water blocks IR, when you get a bubble the IR passes easier and the opto transistor conducts more so raising the voltage. The peaks around the 2 states are effects of the light passing through the edges of the bubble.

The system while operating will see periodic bubbles but while idling could see either days or weeks of air or water

Establishing the peaks is fine on start up as you preload the max and min values so the is code forced to re-find the current max mins. However as the tube gets dirty of the water becomes dirty the amplitude of the signal will change. This and natural degradation of the LED can also cause the levels to drift

So for instance if on startup the max is 435 and the min is 200 then the signal shrinks and drifts lower the min will track the new min value but the max will not. Over time the max and min will get further apart until they move the threshold to a place that can no longer detect the change.

I currently have a system where from start up and seeing bubble and water it performs a fresh max min update I know the state of the system eg water or air. So during a known state I can sample the raw input and get an average and every few seconds (or less for air) it loads the average into the appropriate peak (max or min) vars. As it gets peaks again the the new values are loaded into the max/min vars.

This will work to track any changes to the system as long as they do not happen very quickly and somewhat in sync eg you do not get a shift in signal while stuck in one state

eg if you the system was filled with air so it was only updating the value for the air but then dirty water came through. All my tests are being done in a sim while I wait for a PCB so I can jump the signal around a lot and cause it to get stuck.

The next stage I'm working on is to add a backup system to monitor a jump from a base line that exceeds the minimum jump threshold and if need be get a refresh of the max min initiated.



 

If you can get the amplitude to stay at a certain level, a simple comparator will give the high when the signal's amplitude increases to a particular level, and there is no reason for high and low sampling to see if the state has changed.

It will also be a lot, lot faster. In fact almost real time, because the comparator will trigger an interrupt, so it will be constantly monitored.

Hi Tim,
Instead of using DC coupling what if you used a capacitor to feed an opamp. When a change of state occurs a low frequency click would pass through the system.
With sufficient gain in the opamp you don't have worry about level changes with age.
Trying to think laterally.
John

Hi all

No worries any more as I have it all running. It can so far self adjust to any signal as long as there is a small difference between the peaks. The signal can wander around and change in amplitude and it follows it.
It does though need to see both peaks to get going.

Test cycle is around 140us most of that is the ADC so it could be made faster if started the conversion as I leave the ADC read routine.

AT 140us it's probably a bit faster than I need but can adjust if need be.

Hi Tim

You always have interesting projects. May I ask what this is for?

Best regards
Charlie