Sorting an array

2021-11-25T09:04:35.569000Z

About the MEMCPY/cast in the Compare function: Yes of course a byte per byte comparison is stupid for REAL and also on other types. I was so excited that I forget to remove this commented line of code of my example... shame on me.

We aren't far enough 😅... insertion sort is not that bad but merge sort or quick sort will be really more effective. I am looking to adapt the sort provided in the OSCAT lib to run using a pointer (PVOID) instead of a POINTER TO ARRAY[1..32000] OF REAL. I have some issue with left and right boundaries and/or with the pivot start position. But I will find out soon I hope 😄

My end goal is really to provide a Sort "function" (or class) that can Sort anything using a given compare function. So it will be easy to sort some FB_Biscuit by area size to know which one will get the more chocolate on it 😋

Sorting an array

2021-11-25T09:04:32.256000Z

Sorting an array

2021-11-25T08:03:37.977000Z

I was worried we went a little too far on this topic, but you clearly went a step further.

Just about the real comparaison, real values are store as IEEE format (see : https://en.wikipedia.org/wiki/Single-precision_floating-point_format#IEEE_754_single-precision_binary_floating-point_format:binary32 ). That's a good exemple why you need to type cast and compare values knowing the datatype you are comparing.

great input 👍

Sorting an array

2021-11-24T16:10:30.493000Z

Hi everyone,

I have taken a look of your examples. In other languages we pass a comparison function as a parameter of the sorting function. This is not (or it is?) possible using ST language.

A way to do it may be to create an ABSTRACT FUNCTION_BLOCK FB_Sort with a private Compare and final Sort method. Then in your code you have to create your own FB_Sort_blablabla (example: FB_Sort_REAL) which derivate from the abstract FB_Sort. Then you override the Compare method to fit your needs (like comparing REAL, LREAL, INT, FB_Biscuit, FB_Something, etc…).
You don't have to override the method Sort, it is the same for all your data types.
You don't need to implement anything in the body of your FB_Sort_blablabla.
To sort your array, simply call FB_Sort_blablabla.Sort(insert_all_parameters_as_described).
See code below:

The Abstract function block FB_Sort with abstract method Compare and final method Sort:

FUNCTION_BLOCK ABSTRACT FB_Sort
(*
* Purpose: Run an optimized version of insertion sort with specified order
* Author: NothinRandom
* v1.0  September 16, 2020
* Note:
*)
VAR_INPUT
END_VAR

// No code in the body, the sort algorithm is done using the Sort method
// We could fill the body of this FB with the code of the Sort method
// but then we cannot prevent someone to override it (or it will cause inatended behaviour)

Compare method:

(* Please override this method so it returns:
* 0 : a == b
*-1 : a < b
* 1 : a > b
* which a and b are the ADDRESS of the 2 elements you want to compare
*)
METHOD ABSTRACT Compare : DINT
VAR_INPUT
    a : PVOID;
    b : PVOID;
END_VAR

// No code here since it is an abstract method !!!

Sort method:

METHOD FINAL Sort : BOOL
VAR_INPUT
    pbBuffer    : POINTER TO BYTE; // pointer to buffer
    diElements  : DINT;            // array length
    uiDataSize  : UINT;            // use it like this : uiDataType := SIZEOF(MyDataType) 
                                   // where MyDataType is the type your currently want to compare
    bDescending : BOOL := FALSE;   // default ascending
END_VAR
VAR
    _diIndex            : DINT;                 // loop index
    _diMinIndex         : DINT;                 // loop lowest index tested
    _diMaxIndex         : DINT;                 // loop highest index tested
    _diCurrentIndex     : DINT;                 // loop current tested element index
    _abTemp             : ARRAY [1..8] OF BYTE; // store temp value
    _pbElement1         : PVOID;      // pointer operator, current element
    _pbElement2         : PVOID;      // pointer operator, insert element
    _pCurrent : PVOID;
END_VAR

IF uiDataSize > 8 THEN
    // Not enough space to store the data
    Sort := FALSE;
    RETURN;
END_IF

FOR _diIndex := 1 TO diElements - 1 DO
    // highest index tested
    _diMaxIndex := _diIndex;
    // lowest index tested
    _diMinIndex := -1;
    // element we need to insert
    _pbElement2 := pbBuffer + TO_UDINT(uiDataSize*_diIndex);

    REPEAT
        // current test index
        _diCurrentIndex := _diMinIndex + (_diMaxIndex-_diMinIndex)/2;
        // get element at current test index
        _pbElement1 := pbBuffer + TO_UDINT(uiDataSize*_diCurrentIndex);

        IF (NOT bDescending) THEN
            // IF (_liElement1 > _liElement2) THEN
            IF THIS^.Compare(a := _pbElement1, b := _pbElement2) > 0 THEN
               _diMaxIndex := _diCurrentIndex;
            ELSE
                _diMinIndex := _diCurrentIndex;
            END_IF
        ELSE
            IF THIS^.Compare(a := _pbElement1, b := _pbElement2) > 0 THEN
               _diMinIndex := _diCurrentIndex;
            ELSE
                _diMaxIndex := _diCurrentIndex;
            END_IF
        END_IF

    UNTIL
        _diMaxIndex - _diMinIndex < 2
    END_REPEAT

    // Save value to insert
    MEMCPY(destAddr:=ADR(_abTemp), srcAddr:=_pbElement2, n:=uiDataSize);
    // Move block
    MEMMOVE(destAddr:=pbBuffer+uiDataSize*(TO_UDINT(_diMaxIndex)+1),
            srcAddr:=pbBuffer+TO_UDINT(uiDataSize*_diMaxIndex),
            n:=uiDataSize*TO_UDINT(_diIndex-_diMaxIndex));
    // set key
    MEMCPY(destAddr:=pbBuffer+uiDataSize*TO_UDINT(_diMaxIndex),
           srcAddr:=ADR(_abTemp),
           n:=uiDataSize);
END_FOR

Sort := TRUE;

Ok ... that's for the base of all your future sort function block... Let see an example that can be used to sort REAL type:

First create a new FB which EXTENDS from FB_Sort like this (the FINAL keyword is not necessary):

FUNCTION_BLOCK FINAL FB_Sort_Real EXTENDS FB_Sort
VAR_INPUT
END_VAR
VAR_OUTPUT
END_VAR
VAR
END_VAR

// Leave the body empty

Then, simply override the Compare method:

(* Please override this method so it returns:
* 0 : a == b
*-1 : a < b
* 1 : a > b
* which a and b are the ADDRESS of the 2 elements you want to compare
*)
METHOD  Compare : DINT
VAR_INPUT
    a : PVOID;
    b : PVOID;
END_VAR
VAR
    _a : REAL; // 
    _b : REAL;
END_VAR

// Here I tried a byte per byte comparison
// Unfortunately this is not working with REAL type... maybe little/big endian issue?
// This could also not work with integer type (INT/UINT, DINT/UDINT, ...)
// Compare := MEMCMP(a, b, SIZEOF(REAL));

// The "cast" method will worked in any case and for any type (like for FB_Something)
MEMCPY(destAddr := ADR(_a), srcAddr := a, SIZEOF(REAL)); // does this : _a := a^;
MEMCPY(destAddr := ADR(_b), srcAddr := b, SIZEOF(REAL)); // does this : _b := b^;
IF _a < _b THEN
    Compare := -1;
ELSIF _a > _b THEN
    Compare := 1;
ELSE
    Compare := 0;
END_IF

And I use the code like it somewhere inside my project:

VAR
    array_toto : ARRAY [0..9] OF REAL := 
        [ 0.5, 0.4,  0.9, 0.2, 0.7, 0.3,0.6, 0.8, 0.1, 1.0];

    sort_real : FB_Sort_Real;
END_VAR
---
sort_real.Sort(pbBuffer := ADR(array_toto), 
               diElements := 10,
               uiDataSize := SIZEOF(REAL),
               bDescending := FALSE);

Sorting an array

2020-09-26T03:53:59.920000Z

You're right. I forgot 😉
A workaround for this can be:

VAR_INPUT
    // reference to first element to sort
    array : ANY;
    // number of elements in the array
    num : DINT;
END_VAR

Sorting an array

2020-09-26T01:01:30.999000Z

@Ingo, I tried using datatype ANY at first. However, we're not allowed to have something like ARRAY[1..10] OF ANY_NUM or POINTER TO ARRAY[1..10] OF ANY_NUM, so it can only be ANY_NUM inside VAR_INPUT. I am not sure how we could provide sorting in this scenario. Is it possible to move this thread into Engineering?

Sorting an array

2020-09-25T23:17:47.455000Z

Hi guys!
I guess it is due to the high cost of the
CASE within the loops.

Another interfacing idea was, to use the ANY datatype:
https://forge.codesys.com/tol/iec-snippets/snippets/8/

Then, to optimize the swapping, I would avoid the CASE, and just copy the elements by size (which is defined already by ANY).

What do you think?

Cheers,
Ingo

Sorting an array

2020-09-25T17:23:26.177000Z

Had a look at OSCAT basic, which is implementing quicksort in ARRAYSORT (REAL datatype only).
it's a faster on simulation, sorting 10000 random items is averaging 1ms while my code produces 7ms.
Maybe that's due too the good use of cpu caching by C&D. That would be great to have so measurement on a real PLC.
Or maybe that's worthless reinventing what's already written down 😂

Sorting an array

2020-09-25T17:03:26.766000Z

@dfx, good stuff. Looks that min index needed to be a DINT so that you can shift minimum from 0 to -1.

I've made updates on my end and incorporated your work:

FUNCTION numInsertSort : BOOL
VAR_INPUT
    pbBuffer            : POINTER TO BYTE;      // pointer to buffer
    diElements          : DINT;                 // array length
    uiDataType          : UINT;                 // data type: SINT(1), USINT/BYTE(2), INT(3), UINT/WORD(4), DINT(5), UDINT/DWORD(6), LINT(7), ULINT/LWORD(8), REAL(9), LREAL(10)
    bDescending         : BOOL := FALSE;        // default ascending
END_VAR
VAR
    _uiDataSize         : UINT;                 // element size
    _diIndex            : DINT;                 // loop index
    _diMinIndex         : DINT;                 // loop lowest index tested
    _diMaxIndex         : DINT;                 // loop highest index tested
    _diCurrentIndex     : DINT;                 // loop current tested element index
    _abTemp             : ARRAY [1..8] OF BYTE; // store temp value
    _pbElement1         : POINTER TO BYTE;      // pointer operator, current element
    _pbElement2         : POINTER TO BYTE;      // pointer operator, insert element
    _liElement1         : LINT;
    _liElement2         : LINT;
    _uliElement1        : ULINT;
    _uliElement2        : ULINT;
    _rElement1          : REAL;
    _rElement2          : REAL;
    _lrElement1         : LREAL;
    _lrElement2         : LREAL;
END_VAR

================================================================================================================

CASE uiDataType OF
    1,2: // SINT, USINT/BYTE
        _uiDataSize := 1;
    3,4: // INT, UINT/WORD
        _uiDataSize := 2;
    5,6,9: // DINT, UDINT/DWORD, REAL
        _uiDataSize := 4;
    7,8,10: // LINT, ULINT/LWORD, LREAL
        _uiDataSize := 8;
ELSE
    RETURN;
END_CASE

FOR _diIndex := 1 TO diElements - 1 DO
    // highest index tested
    _diMaxIndex := _diIndex;
    // lowest index tested
    _diMinIndex := -1;
    // element we need to insert
    _pbElement2 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex);
    REPEAT
        // current test index
        _diCurrentIndex := _diMinIndex + (_diMaxIndex-_diMinIndex)/2;
        // get element at current test index
        _pbElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diCurrentIndex);
        CASE uiDataType OF
            1,3,5,7: // SINT, INT, DINT, LINT
                // test for ordering
                SysMemCpy(pDest:=ADR(_liElement1), pSrc:=_pbElement1, udiCount:=_uiDataSize);
                SysMemCpy(pDest:=ADR(_liElement2), pSrc:=_pbElement2, udiCount:=_uiDataSize);
                IF (NOT bDescending) THEN
                    IF (_liElement1 > _liElement2) THEN
                       _diMaxIndex := _diCurrentIndex;
                    ELSE
                        _diMinIndex := _diCurrentIndex;
                    END_IF
                ELSE
                    IF (_liElement1 > _liElement2) THEN
                       _diMinIndex := _diCurrentIndex;
                    ELSE
                        _diMaxIndex := _diCurrentIndex;
                    END_IF
                END_IF
            2,4,6,8: // USINT/BYTE, UINT/WORD, UDINT/DWORD, ULINT/LWORD
                // test for ordering
                SysMemCpy(pDest:=ADR(_uliElement1), pSrc:=_pbElement1, udiCount:=_uiDataSize);
                SysMemCpy(pDest:=ADR(_uliElement2), pSrc:=_pbElement2, udiCount:=_uiDataSize);
                IF (NOT bDescending) THEN
                    IF (_uliElement1 > _uliElement2) THEN
                       _diMaxIndex := _diCurrentIndex;
                    ELSE
                        _diMinIndex := _diCurrentIndex;
                    END_IF
                ELSE
                    IF (_uliElement1 > _uliElement2) THEN
                       _diMinIndex := _diCurrentIndex;
                    ELSE
                        _diMaxIndex := _diCurrentIndex;
                    END_IF
                END_IF
            9: // REAL
                // test for ordering
                SysMemCpy(pDest:=ADR(_rElement1), pSrc:=_pbElement1, udiCount:=_uiDataSize);
                SysMemCpy(pDest:=ADR(_rElement2), pSrc:=_pbElement2, udiCount:=_uiDataSize);                
                IF (NOT bDescending) THEN
                    IF (_rElement1 > _rElement2) THEN
                        _diMaxIndex := _diCurrentIndex;
                    ELSE
                        _diMinIndex := _diCurrentIndex;
                    END_IF
                ELSE
                    IF (_rElement1 > _rElement2) THEN
                        _diMinIndex := _diCurrentIndex;
                    ELSE
                        _diMaxIndex := _diCurrentIndex;
                    END_IF
                END_IF
            10: // LREAL
                // test for ordering
                SysMemCpy(pDest:=ADR(_lrElement1), pSrc:=_pbElement1, udiCount:=_uiDataSize);
                SysMemCpy(pDest:=ADR(_lrElement2), pSrc:=_pbElement2, udiCount:=_uiDataSize);
                IF (NOT bDescending) THEN
                    IF (_lrElement1 > _lrElement2) THEN
                        _diMaxIndex := _diCurrentIndex;
                    ELSE
                        _diMinIndex := _diCurrentIndex;
                    END_IF
                ELSE
                    IF (_lrElement1 > _lrElement2) THEN
                        _diMinIndex := _diCurrentIndex;
                    ELSE
                        _diMaxIndex := _diCurrentIndex;
                    END_IF
                END_IF
        END_CASE
    UNTIL
        _diMaxIndex - _diMinIndex < 2
    END_REPEAT
    // Save value to insert
    SysMemCpy(pDest:=ADR(_abTemp), pSrc:=_pbElement2, udiCount:=_uiDataSize);
    // Move block
    SysMemMove(pDest:=pbBuffer+_uiDataSize*(TO_UDINT(_diMaxIndex)+1), pSrc:=pbBuffer+TO_UDINT(_uiDataSize*_diMaxIndex), udiCount:=_uiDataSize*TO_UDINT(_diIndex-_diMaxIndex));
    // set key
    SysMemCpy(pDest:=pbBuffer+_uiDataSize*TO_UDINT(_diMaxIndex), pSrc:=ADR(_abTemp), udiCount:=_uiDataSize);
END_FOR

numInsertSort := TRUE;

Sorting an array

2020-09-25T11:51:52.507000Z

@nothinrandom(https://forge.codesys.com/u/nothinrandom/)

Fixed code with some cleanup.

Feel free to add it to your base.

FUNCTION numInsertSort : BOOL
VAR_INPUT
    pbBuffer                : POINTER TO BYTE;      // pointer to buffer
    diElements              : DINT;                 // array length
    uiDataType              : UINT;                 // data type: SINT(1), USINT/BYTE(2), INT(3), UINT/WORD(4), DINT(5), UDINT/DWORD(6), LINT(7), ULINT/LWORD(8), REAL(9), LREAL(10)
    bOrder                  : BOOL := FALSE;        // default ascending
END_VAR
VAR
    _uiDataSize             : UINT;                 // element size
    _diIndex1               : DINT;                 // loop index
    _diMaxIndex             : DINT;                 // loop highest index tested
    _diMinIndex             : DINT;                 // loop lowest index tested
    _diCurrentIndex         : DINT;                 // loop current tested element index
    _bSwapped               : BOOL;                 // optimization
    _pbTemp                 : POINTER TO BYTE;      // pointer to temp
    _psiInsertElement       : POINTER TO REAL;      // pointer operator
    _psiCurrentElement      : POINTER TO REAL;      // pointer operator
    _abTemp                 : ARRAY [1..8] OF BYTE; // store temp value
END_VAR

_uiDataSize := 4;
FOR _diIndex1 := 1 TO diElements - 1 DO
    // highest index tested
    _diMaxIndex := _diIndex1;
    // lowest index tested
    _diMinIndex := -1;
    // element we need to insert
    _psiInsertElement := pbBuffer + DINT_TO_DWORD(_uiDataSize*_diIndex1);
    REPEAT
        // current test index
        _diCurrentIndex :=  _diMinIndex + TRUNC((_diMaxIndex - _diMinIndex)/ 2);
        // get element at current test index
        _psiCurrentElement :=pbBuffer + DINT_TO_DWORD(_uiDataSize*_diCurrentIndex);
        // test for ordering
        IF _psiCurrentElement^ > _psiInsertElement^ THEN
            // ascending / descending
            IF NOT (bOrder) THEN
               _diMaxIndex := _diCurrentIndex;
            ELSE
               _diMinIndex := _diCurrentIndex;
            END_IF
        ELSE
            // ascending / descending
            IF NOT (bOrder) THEN
               _diMinIndex := _diCurrentIndex;
            ELSE
               _diMaxIndex := _diCurrentIndex;
            END_IF;
        END_IF;
    UNTIL
        _diMaxIndex - _diMinIndex < 2
    END_REPEAT
    // Save value to insert
    SysMemCpy(pDest:=ADR(_abTemp), pSrc:=_psiInsertElement, udiCount:=_uiDataSize);
    // Move block
    SysMemMove(pDest:=pbBuffer+DINT_TO_DWORD(_uiDataSize*(_diMaxIndex+1)) , pSrc:=pbBuffer+DINT_TO_DWORD(_uiDataSize*_diMaxIndex) , udiCount:=DINT_TO_DWORD(_uiDataSize*(_diIndex1 - _diMaxIndex) ));
    // set key
    SysMemCpy(pDest:=pbBuffer+DINT_TO_DWORD(_uiDataSize*_diMaxIndex), pSrc:=ADR(_abTemp), udiCount:=_uiDataSize);

END_FOR

numInsertSort := TRUE;

Recent posts to Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array

Sorting an array