Welcome to our new forum
All users of the legacy CODESYS Forums, please create a new account at account.codesys.com. But make sure to use the same E-Mail address as in the old Forum. Then your posts will be matched. Close

Sorting an array

NBCC
2017-08-22
2021-11-25
1 2 > >> (Page 1 of 2)
  • NBCC - 2017-08-22

    Hi all,

    I was wondering how you can sort out an array. I have around 50 values stacked in it. They are all mixed and i want to know if i can get the highest values first and the lowest values should be in the bottom. I have no idea how it is done. I was thinking with a for-loop but still can't figure it out.
    Has anyone got experience with this?

    Many thanks

     
  • teichhei - 2017-08-23

    Hi,

    You are on the right track. You need to compare each index with the next and swap if the value is bigger.
    You need two loops stacked in each other running them both for each element. Have a play, if you can't get it going I post an example.

    Sent from my SM-G935F using Tapatalk

     
  • Lo5tNet - 2017-08-23

    Here is a quick and dirty way of doing it. I'm using version 3.5.5.0 so I don't have access to a lot of the new array features so I still pass pointers.

    FUNCTION SORTARRAY : BOOL
    VAR_INPUT
       ptrSortArray            :      POINTER TO ARRAY[0..0] OF INT;
       nArraySize               :      UINT;
       xSortDescending            :      BOOL;
    END_VAR
    VAR
       nCurrentLocation         :      UINT;
       nInnerLocation            :      UINT;
       ptrSmallerValue            :      POINTER TO INT;
       ptrLargerValue            :      POINTER TO INT;
       sTempValue               :      INT;
    END_VAR
    FOR nCurrentLocation := 0 TO nArraySize DO
       IF xSortDescending THEN
          ptrLargerValue := ADR(ptrSortArray[nCurrentLocation]);
       ELSE
          ptrSmallerValue := ADR(ptrSortArray[nCurrentLocation]);
       END_IF
       FOR nInnerLocation := (nCurrentLocation + 1) TO nArraySize DO
          IF xSortDescending THEN
             IF ptrSortArray^[nInnerLocation] > ptrLargerValue^ THEN
                ptrLargerValue := ADR(ptrSortArray[nInnerLocation]);
             END_IF
          ELSE
             IF ptrSortArray^[nInnerLocation] < ptrSmallerValue^ THEN
                ptrSmallerValue := ADR(ptrSortArray[nInnerLocation]);
             END_IF
          END_IF
       END_FOR
       sTempValue := ptrSortArray^[nCurrentLocation];
       IF xSortDescending THEN
          ptrSortArray^[nCurrentLocation] := ptrLargerValue^;
          ptrLargerValue^ := sTempValue;
       ELSE
          ptrSortArray^[nCurrentLocation] := ptrSmallerValue^;
          ptrSmallerValue^ := sTempValue;
       END_IF
    END_FOR
    

    Then to call it:

    PROGRAM PLC_PRG
    VAR
    //Test sort array
       aSorted                  :   ARRAY[0..nArraySize] OF INT;
       xRunSort               :   BOOL;
       xDescending               :   BOOL;
    END_VAR
    VAR CONSTANT
       nArraySize               :   INT                  :=   9;
    END_VAR
    IF xRunSort THEN
       SORTARRAY(ptrSortArray:= ADR(aSorted), nArraySize:= nArraySize, xSortDescending:= xDescending);
       xRunSort := FALSE;
    END_IF
    

    This was quickly thrown together so no guarantees but hope it at least gets you started.

     
  • NBCC - 2017-08-31

    Thanks a lot
    I had some other work to do (that's why my reply is a little late) but i'll try it out

     
  • NBCC - 2017-09-06

    Ok so i worked something out. Works perfect for me. Just want to share this

    IF sort THEN
    sort := FALSE; (visualisation stuff)
    FOR x := 1 TO max DO
    FOR y := 1 TO max-1 DO
    IF value[y] < value[y+1] THEN
    temp[1] := Value[y+1];
    Value[y+1] := Value[y];
    Value[e] := temp[1];
    END_IF
    END_FOR
    END_FOR
    END_IF

     

    Related

    Talk.ru: 1

  • Lo5tNet - 2017-09-06

    Hey NBCC,
    Thanks for posting your attempt at trying to come up with your own solution.
    Are there errors in your logic that happened when you copied onto here as I see some questionable areas that wouldn't work.
    1. I think "Value[e] := temp[1];" should actually be "Value[x] := temp[1];"
    2. You are never comparing X to anything.
    3. Using max as a variable couldn't be done. Maybe you just renamed this?
    4. When using your code with values 9,6,2,8,1,7,5,5,4,3 the results after sorting are 3,3,3,3,3,3,3,3,3,6.

    Hopefully the errors just happened when you copied it.

     

    Related

    Talk.ru: 1

  • NBCC - 2017-09-07

    Comingback4u hat geschrieben:
    Hey NBCC,
    Thanks for posting your attempt at trying to come up with your own solution.
    Are there errors in your logic that happened when you copied onto here as I see some questionable areas that wouldn't work.
    1. I think "Value[e] := temp[1];" should actually be "Value[x] := temp[1];"
    2. You are never comparing X to anything.
    3. Using max as a variable couldn't be done. Maybe you just renamed this?
    4. When using your code with values 9,6,2,8,1,7,5,5,4,3 the results after sorting are 3,3,3,3,3,3,3,3,3,6.
    Hopefully the errors just happened when you copied it.

    Ok looks like i made some mistakes. I changed the code a little bit to make it look easier but maybe i should have given a little explanation.

    1. The Value[e] := temp[1] should be Value[y] := temp[1]; this is a temporary value
    2. X will just run to the value max (point 3 will explain what max means). No need to compare it with anything
    3. I changed the name. With max i mean the last row of the array (the array i get is always a different size) So if you got 6 values then x will run to 6, etc.
    4. Maybe you got those values because of my bad explanation in my previous post.

    Hope this works for you. If not, please let me know

     

    Related

    Talk.ru: 1

  • Anonymous - 2017-09-13

    Originally created by: scott_cunningham

    Please take care of your execution time - as your list grows, you will create a large execution time and potentially create a PLC execution fault. If you use this solution (bubble sort) with motion control systems, you can have issues. Either modify the code so it only loops XX number of times per PLC scan or move it to a low priority task.

     
  • StoeberAs - 2020-01-30

    VAR_INPUT
    pT:POINTER TO INT;
    size:UINT;
    END_VAR
    VAR
    i:INT;
    iActualSize :UINT;
    iTemp :INT;
    j: INT;
    pCompare:POINTER TO INT;
    END_VAR

    iActualSize:=Size/SIZEOF(pT^);
    FOR i:=1 TO iActualSize-1 DO
    FOR j:=1 TO iActualSize-1 DO
    pCompare:=pT+SIZEOF(pT^);
    IF pT^>pCompare^ THEN
    iTemp:=pCompare^;
    pCompare^:= pT^;
    pT^:=iTemp;
    END_IF
    pT:=pT+SIZEOF(pT^);
    END_FOR
    pT:=pT-(iActualSize-1)*2;
    END_FOR

     
  • dFx

    dFx - 2020-03-03

    If you are interested into optimizing the sort, then, this is how .net framework handle unidimensional array sorting :

    If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm.

    If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.

    Otherwise, it uses a Quicksort algorithm

    Source : https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?view=netframework-4.8#System_Array_Sort_System_Array_

     
  • nothinrandom - 2020-09-16

    Hey All. This looks interesting and I didn't find something flexible, so below is an attempt. To use the following code is relatively straight forward. Let's say you have some arrays. (Disclaimer: wrote this during lunch, so I am sure there is room for improvement)

    asiTest : ARRAY [1..10] OF SINT := [-5, 1, 8, -9, 12, -51, 11, 3, 3, 2];
    arTest : ARRAY [1..20] OF REAL := [5.1, 1.2, 8.001, 9.1, 12.4, 51, 11.1, 3.1, 3.2, 2.3, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 10.10];
    

    To sort SINT array in ascending order:

    // using LOWER_BOUND/UPPER_BOUND, but you can hard code directly
    numBubbleSort(pbBuffer:=ADR(asiTest), diElements:=TO_UDINT(UPPER_BOUND(asiTest,1)-LOWER_BOUND(asiTest,1))+1, uiDataType:=1);
    

    To sort SINT array in descending order:

    numBubbleSort(pbBuffer:=ADR(asiTest), diElements:=TO_UDINT(UPPER_BOUND(asiTest,1)-LOWER_BOUND(asiTest,1))+1, uiDataType:=1, bOrder:=TRUE);
    

    To sort real array in ascending order:

    numBubbleSort(pbBuffer:=ADR(arTest), diElements:=TO_UDINT(UPPER_BOUND(arTest,1)-LOWER_BOUND(arTest,1))+1, uiDataType:=9);
    
    (*
    
    Purpose: Run an optimized version of bubble sort with specified order
    
    * Author: NothinRandom
    * v1.0  September 16, 2020
    * Note:
    
    *)
    FUNCTION numBubbleSort : BOOL
    VAR_INPUT
        pbBuffer        : POINTER TO BYTE;      // pointer to buffer
        udiElements     : UDINT;                // 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
        _udiIndex1      : UDINT;                // loop index
        _udiIndex2      : UDINT;                // loop index
        _bSwapped       : BOOL;                 // optimization
        _abTemp         : ARRAY [1..8] OF BYTE; // store temp value
        _pbTemp         : POINTER TO BYTE;      // pointer to temp
        _psiElement1    : POINTER TO SINT;      // pointer operator
        _psiElement2    : POINTER TO SINT;      // pointer operator
        _pbElement1     : POINTER TO BYTE;      // pointer operator
        _pbElement2     : POINTER TO BYTE;      // pointer operator
        _piElement1     : POINTER TO INT;       // pointer operator
        _piElement2     : POINTER TO INT;       // pointer operator
        _puiElement1    : POINTER TO UINT;      // pointer operator
        _puiElement2    : POINTER TO UINT;      // pointer operator
        _pdiElement1    : POINTER TO DINT;      // pointer operator
        _pdiElement2    : POINTER TO DINT;      // pointer operator
        _pudiElement1   : POINTER TO UDINT;     // pointer operator
        _pudiElement2   : POINTER TO UDINT;     // pointer operator
        _pliElement1    : POINTER TO LINT;      // pointer operator
        _pliElement2    : POINTER TO LINT;      // pointer operator
        _puliElement1   : POINTER TO ULINT;     // pointer operator
        _puliElement2   : POINTER TO ULINT;     // pointer operator
        _prElement1     : POINTER TO REAL;      // pointer operator
        _prElement2     : POINTER TO REAL;      // pointer operator
        _plrElement1    : POINTER TO LREAL;     // pointer operator
        _plrElement2    : POINTER TO LREAL;     // pointer operator
    END_VAR
    
    ===============================================================================
    
    CASE uiDataType OF
        1: // SINT
            _psiElement1 := pbBuffer;
            _uiDataSize := 1;
        2: // USINT/BYTE
            _pbElement1 := pbBuffer;
            _uiDataSize := 1;
        3: // INT
            _piElement1 := pbBuffer;
            _uiDataSize := 2;
        4: // UINT/WORD
            _puiElement1 := pbBuffer;
            _uiDataSize := 2;
        5: // DINT
            _pdiElement1 := pbBuffer;
            _uiDataSize := 4;
        6: // UDINT/DWORD
            _pudiElement1 := pbBuffer;
            _uiDataSize := 4;
        7: // LINT
            _pliElement1 := pbBuffer;
            _uiDataSize := 8;
        8: // ULINT/LWORD
            _puliElement1 := pbBuffer;
            _uiDataSize := 8;
        9: // REAL
            _prElement1 := pbBuffer;
            _uiDataSize := 4;
        10: // LREAL
            _plrElement1 := pbBuffer;
            _uiDataSize := 8;
    ELSE
        RETURN;
    END_CASE
    
    // get reference pointer
    _pbTemp := ADR(_abTemp);
    
    FOR _udiIndex1 := 1 TO udiElements - 1 DO
        _bSwapped := FALSE;
        FOR _udiIndex2 := 1 TO udiElements - _udiIndex1 DO
            CASE uiDataType OF
                1: // SINT
                    _psiElement2 := _psiElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _psiElement1^ > _psiElement2^;
                    ELSE
                        _bSwapped := _psiElement1^ < _psiElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_psiElement2, udiCount:=_uiDataSize);
                        _psiElement2^ := _psiElement1^;
                        SysMemCpy(pDest:=_psiElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _psiElement1 := _psiElement1 + _uiDataSize;
                2: // USINT/BYTE
                    _pbElement2 := _pbElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _pbElement1^ > _pbElement2^;
                    ELSE
                        _bSwapped := _pbElement1^ < _pbElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_pbElement2, udiCount:=_uiDataSize);
                        _pbElement2^ := _pbElement1^;
                        SysMemCpy(pDest:=_pbElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _pbElement1 := _pbElement1 + _uiDataSize;
                3: // INT
                    _piElement2 := _piElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _piElement1^ > _piElement2^;
                    ELSE
                        _bSwapped := _piElement1^ < _piElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_piElement2, udiCount:=_uiDataSize);
                        _piElement2^ := _piElement1^;
                        SysMemCpy(pDest:=_piElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _piElement1 := _piElement1 + _uiDataSize;
                4: // UINT/WORD
                    _puiElement2 := _puiElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _puiElement1^ > _puiElement2^;
                    ELSE
                        _bSwapped := _puiElement1^ < _puiElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_puiElement2, udiCount:=_uiDataSize);
                        _puiElement2^ := _puiElement1^;
                        SysMemCpy(pDest:=_puiElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _puiElement1 := _puiElement1 + _uiDataSize;
                5: // DINT
                    _pdiElement2 := _pdiElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _pdiElement1^ > _pdiElement2^;
                    ELSE
                        _bSwapped := _pdiElement1^ < _pdiElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_pdiElement2, udiCount:=_uiDataSize);
                        _pdiElement2^ := _pdiElement1^;
                        SysMemCpy(pDest:=_pdiElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _pdiElement1 := _pdiElement1 + _uiDataSize;
                6: // UDINT/DWORD
                    _pudiElement2 := _pudiElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _pudiElement1^ > _pudiElement2^;
                    ELSE
                        _bSwapped := _pudiElement1^ > _pudiElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_pudiElement2, udiCount:=_uiDataSize);
                        _pudiElement2^ := _pudiElement1^;
                        SysMemCpy(pDest:=_pudiElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _pudiElement1 := _pudiElement1 + _uiDataSize;
                7: // LINT
                    _pliElement2 := _pliElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _pliElement1^ > _pliElement2^;
                    ELSE
                        _bSwapped := _pliElement1^ < _pliElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_pliElement2, udiCount:=_uiDataSize);
                        _pliElement2^ := _pliElement1^;
                        SysMemCpy(pDest:=_pliElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _pliElement1 := _pliElement1 + _uiDataSize;
                8: // ULINT/LWORD
                    _puliElement2 := _puliElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _puliElement1^ > _puliElement2^;
                    ELSE
                        _bSwapped := _puliElement1^ < _puliElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_puliElement2, udiCount:=_uiDataSize);
                        _puliElement2^ := _puliElement1^;
                        SysMemCpy(pDest:=_puliElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _puliElement1 := _puliElement1 + _uiDataSize;
                9: // REAL
                    _prElement2 := _prElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _prElement1^ > _prElement2^;
                    ELSE
                        _bSwapped := _prElement1^ < _prElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_prElement2, udiCount:=_uiDataSize);
                        _prElement2^ := _prElement1^;
                        SysMemCpy(pDest:=_prElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _prElement1 := _prElement1 + _uiDataSize;
                10: // LREAL
                    _plrElement2 := _plrElement1 + _uiDataSize;
                    IF NOT (bDescending) THEN
                        _bSwapped := _plrElement1^ > _plrElement2^;
                    ELSE
                        _bSwapped := _plrElement1^ < _plrElement2^;
                    END_IF
                    IF (_bSwapped) THEN
                        // store temp value, and swap
                        SysMemCpy(pDest:=_pbTemp, pSrc:=_plrElement2, udiCount:=_uiDataSize);
                        _plrElement2^ := _plrElement1^;
                        SysMemCpy(pDest:=_plrElement1, pSrc:=_pbTemp, udiCount:=_uiDataSize);
                    END_IF
                    _plrElement1 := _plrElement1 + _uiDataSize;
            END_CASE
        END_FOR
        // exit if already sorted
        IF (NOT _bSwapped) THEN EXIT; END_IF
        CASE uiDataType OF
            1: // SINT
                _psiElement1 := pbBuffer;
            2: // USINT/BYTE
                _pbElement1 := pbBuffer;
            3: // INT
                _piElement1 := pbBuffer;
            4: // UINT/WORD
                _puiElement1 := pbBuffer;
            5: // DINT
                _pdiElement1 := pbBuffer;
            6: // UDINT/DWORD
                _pudiElement1 := pbBuffer;
            7: // LINT
                _pliElement1 := pbBuffer;
            8: // ULINT/LWORD
                _puliElement1 := pbBuffer;
            9: // REAL
                _prElement1 := pbBuffer;
            10: // LREAL
                _plrElement1 := pbBuffer;
        END_CASE
    END_FOR
    
    numBubbleSort := TRUE;
    
     

    Last edit: nothinrandom 2020-09-24
  • nothinrandom - 2020-09-17

    Previous code uses bubble sort, which is easier to implement but not so great in performance. Below is an implementation of insertion sort, which is arguably better.

    asiTest : ARRAY [1..10] OF SINT := [-5, 1, 8, -9, 12, -51, 11, 3, 3, 2];
    arTest : ARRAY [1..20] OF REAL := [5.1, 1.2, 8.001, 9.1, 12.4, 51, 11.1, 3.1, 3.2, 2.3, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 10.10];
    

    To sort SINT array in ascending order:

    // using LOWER_BOUND/UPPER_BOUND, but you can hard code directly
    numInsertSort(pbBuffer:=ADR(asiTest), udiElements:=UPPER_BOUND(asiTest,1)-LOWER_BOUND(asiTest,1)+1, uiDataType:=1);
    

    To sort SINT array in descending order:

    numInsertSort(pbBuffer:=ADR(asiTest), udiElements:=UPPER_BOUND(asiTest,1)-LOWER_BOUND(asiTest,1)+1, uiDataType:=1, bOrder:=TRUE);
    

    To sort real array in ascending order:

    numInsertSort(pbBuffer:=ADR(arTest), udiElements:=UPPER_BOUND(arTest,1)-LOWER_BOUND(arTest,1)+1, uiDataType:=9);
    
    (*
    
    Purpose: Run an optimized version of insertion sort with specified order
    
    * Author: NothinRandom
    * v1.0  September 16, 2020
    * Note:
    
    *)
    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(4), dint(5), udint(6), lint(7), ulint(8), real(9), lreal(10)
        bOrder          : BOOL := FALSE;        // default ascending
    END_VAR
    VAR
        _uiDataSize     : UINT;                 // element size
        _udiIndex1      : UDINT;                // loop index
        _udiIndex2      : UDINT;                // loop index
        _bSwapped       : BOOL;                 // optimization
        _abTemp         : ARRAY [1..8] OF BYTE; // store temp value
        _pbTemp         : POINTER TO BYTE;      // pointer to temp
        _psiElement1    : POINTER TO SINT;      // pointer operator
        _psiElement2    : POINTER TO SINT;      // pointer operator
        _pbElement1     : POINTER TO BYTE;      // pointer operator
        _pbElement2     : POINTER TO BYTE;      // pointer operator
        _piElement1     : POINTER TO INT;       // pointer operator
        _piElement2     : POINTER TO INT;       // pointer operator
        _puiElement1    : POINTER TO UINT;      // pointer operator
        _puiElement2    : POINTER TO UINT;      // pointer operator
        _pdiElement1    : POINTER TO DINT;      // pointer operator
        _pdiElement2    : POINTER TO DINT;      // pointer operator
        _pudiElement1   : POINTER TO UDINT;     // pointer operator
        _pudiElement2   : POINTER TO UDINT;     // pointer operator
        _pliElement1    : POINTER TO LINT;      // pointer operator
        _pliElement2    : POINTER TO LINT;      // pointer operator
        _puliElement1   : POINTER TO ULINT;     // pointer operator
        _puliElement2   : POINTER TO ULINT;     // pointer operator
        _prElement1     : POINTER TO REAL;      // pointer operator
        _prElement2     : POINTER TO REAL;      // pointer operator
        _plrElement1    : POINTER TO LREAL;     // pointer operator
        _plrElement2    : POINTER TO LREAL;     // pointer operator
    END_VAR
    
    ===============================================================================
    
    CASE uiDataType OF
        1,2: // SINT, USINT, BYTE
            _uiDataSize := 1;
        3,4: // INT, UINT
            _uiDataSize := 2;
        5,6,9: // DINT, UDINT, REAL
            _uiDataSize := 4;
        7,8,10: // LINT, ULINT, LREAL
            _uiDataSize := 8;
    ELSE
        RETURN;
    END_CASE
    
    // get reference pointer
    _pbTemp := ADR(_abTemp);
    
    FOR _diIndex1 := 1 TO diElements - 1 DO
        _testCounter := _testCounter + 1;
        // get key
        SysMemCpy(pDest:=_pbTemp, pSrc:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex1), udiCount:=_uiDataSize);
        _diIndex2 := TO_DINT(_diIndex1 - 1);
        CASE uiDataType OF
            1: // SINT
                _psiElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _psiElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _psiElement1^ > _psiElement2^;
                    ELSE
                        _bSwapped := _psiElement1^ < _psiElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_psiElement1+_uiDataSize, pSrc:=_psiElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            2: // USINT/BYTE
                _pbElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _pbElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _pbElement1^ > _pbElement2^;
                    ELSE
                        _bSwapped := _pbElement1^ < _pbElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_pbElement1+_uiDataSize, pSrc:=_pbElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            3: // INT
                _piElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _piElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _piElement1^ > _piElement2^;
                    ELSE
                        _bSwapped := _piElement1^ < _piElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_piElement1+_uiDataSize, pSrc:=_piElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                    _testCounter := _testCounter + 1;
                END_WHILE
            4: // UINT
                _puiElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _puiElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _puiElement1^ > _puiElement2^;
                    ELSE
                        _bSwapped := _puiElement1^ < _puiElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_puiElement1+_uiDataSize, pSrc:=_puiElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            5: // DINT
                _pdiElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _pdiElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _pdiElement1^ > _pdiElement2^;
                    ELSE
                        _bSwapped := _pdiElement1^ < _pdiElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_pdiElement1+_uiDataSize, pSrc:=_pdiElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            6: // UDINT
                _pudiElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _pudiElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _pudiElement1^ > _pudiElement2^;
                    ELSE
                        _bSwapped := _pudiElement1^ < _pudiElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_pudiElement1+_uiDataSize, pSrc:=_pudiElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            7: // LINT
                _pliElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _pliElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _pliElement1^ > _pliElement2^;
                    ELSE
                        _bSwapped := _pliElement1^ < _pliElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_pliElement1+_uiDataSize, pSrc:=_pliElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            8: // ULINT
                _puliElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _puliElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _puliElement1^ > _puliElement2^;
                    ELSE
                        _bSwapped := _puliElement1^ < _puliElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_puliElement1+_uiDataSize, pSrc:=_puliElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            9: // REAL
                _prElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _prElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _prElement1^ > _prElement2^;
                    ELSE
                        _bSwapped := _prElement1^ < _prElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_prElement1+_uiDataSize, pSrc:=_prElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
            10: // LREAL
                _plrElement2 := _pbTemp;
                WHILE (_diIndex2 >= 0) DO
                    _plrElement1 := pbBuffer + TO_UDINT(_uiDataSize*_diIndex2);
                    // ascending / descending
                    IF NOT (bOrder) THEN
                        _bSwapped := _plrElement1^ > _plrElement2^;
                    ELSE
                        _bSwapped := _plrElement1^ < _plrElement2^;
                    END_IF
                    IF (NOT _bSwapped) THEN EXIT; END_IF
                    // next = current
                    SysMemCpy(pDest:=_plrElement1+_uiDataSize, pSrc:=_plrElement1, udiCount:=_uiDataSize);
                    _diIndex2 := _diIndex2 - 1;
                END_WHILE
        END_CASE
        // set key
        SysMemCpy(pDest:=pbBuffer+_uiDataSize*(TO_UDINT(_diIndex2)+1), pSrc:=_pbTemp, udiCount:=_uiDataSize);
    END_FOR
    
    numInsertSort := TRUE;
    
     
    👍
    1

    Last edit: nothinrandom 2020-09-24
  • dFx

    dFx - 2020-09-17

    Great work.

    Could you imagine adding some index optimization ? If elements are swapped, then approximate the new index by halving the distance to the max possible (needs two index memory more). This is a pretty good optimization in case of large arrays, almost square rooting the number of tests needed to insert correctly.

    Anyway, Kudos to you.

     
    👍
    1
    • nothinrandom - 2020-09-17

      Thanks! Yeah, I'm also exploring other sorting algorithms (e.g. quick, selection and potentially heap), but they get pretty complex to write in structured text. Forgot that USINT is equivalent to a BYTE, so I'll update the code above.

       
      👍
      1

      Last edit: nothinrandom 2020-09-17
    • nothinrandom - 2020-09-18

      @dFx, not sure what you meant by "If elements are swapped, then approximate the new index by halving the distance to the max possible (needs two index memory more)."

       
  • dFx

    dFx - 2020-09-18

    first of all, don't try to place the inserted element at the end, but test at the actual halved length element. If it is lower and you are going for ascending, then add the halved remaining number of elements to the top, and repeat. Repeat whole till the last lower checked element and the last upper checked element are contiguous.

     
    👍
    1
    • nothinrandom - 2020-09-24

      Have you worked this out yet? Something even in psuedo-code would be useful since I do not see how shifting the elements will increase performance. Maybe in a special scenario it might?

       
      • dFx

        dFx - 2020-09-24

        This a dirty example, tested with reals.

        The purpose is to skip some items testing. This is an insertion sort, and it is expected to be ineffective on small arrays. But on large ones, it should almost square root the processing time.
        I've did some modifications to your code template because of unsigned convertion warnings (on 3.5.12.6).

        FUNCTION numInsertSort : BOOL
        VAR_INPUT
            pbBuffer        : POINTER TO BYTE;      // pointer to buffer
            udiElements      : UDINT;                // 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
            _udiIndex1               : UDINT;                 // loop index
            _udiMaxIndex         : UDINT;                 // loop highest index tested
                    _udiMinIndex              : UDINT;                 // loop lowest index tested
                    _udiCurrentIndex       : UDINT;                                                         // 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 _udiIndex1 := 1 TO udiElements - 1 DO
                    // highest index tested
                    _udiMaxIndex := _udiIndex1;
                    // lowest index tested
                    _udiMinIndex := 0;
                    // element we need to intsert
                    _psiInsertElement := pbBuffer + _uiDataSize*_udiIndex1;
                    REPEAT
                                // current test index
                                _udiCurrentIndex := _udiMinIndex + DINT_TO_UDINT(TRUNC((_udiMaxIndex - _udiMinIndex)/ 2));
                                // get element at current test index
                                _psiCurrentElement :=pbBuffer + _uiDataSize*_udiCurrentIndex;
                                // test for ordering
                                IF _psiCurrentElement^ > _psiInsertElement^ THEN
                                            // ascending / descending
                                            IF NOT (bOrder) THEN
                                                       _udiMaxIndex := _udiCurrentIndex;
                                            ELSE
                                                       _udiMinIndex := _udiCurrentIndex;
                                            END_IF
                                ELSE
                                            // ascending / descending
                                            IF NOT (bOrder) THEN
                                                       _udiMinIndex := _udiCurrentIndex;
                                            ELSE
                                                       _udiMaxIndex := _udiCurrentIndex;
                                            END_IF;
                                END_IF;
                    UNTIL
                                _udiMaxIndex - _udiMinIndex < 2
                    END_REPEAT
                    // Save value to insert
                    SysMemCpy(pDest:=ADR(_abTemp), pSrc:=_psiInsertElement, udiCount:=_uiDataSize);
                    // Move block
                    SysMemMove(pDest:=pbBuffer+_uiDataSize*(_udiMaxIndex+1) , pSrc:=pbBuffer+_uiDataSize*_udiMaxIndex , udiCount:=_uiDataSize*(_udiIndex1 - _udiMaxIndex) );
            // set key
            SysMemCpy(pDest:=pbBuffer+_uiDataSize*_udiMaxIndex, pSrc:=ADR(_abTemp), udiCount:=_uiDataSize);
        END_FOR
        
        numInsertSort := TRUE;
        
         
        👍
        1

        Last edit: dFx 2020-09-24
        • nothinrandom - 2020-09-24

          @dFx, Excellent work! I sorted arrays of N=10, 100, 200, 400, 800 REAL.

          To measure my cycles/steps, I inserted a counter right after the for loop statement, and another inside the while loop.

          To measure your cycles/steps, I inserted a counter before the repeat (for loop) and again inside the DoWhile loop.

              _testCounter := _testCounter + 1;
              REPEAT
                  _testCounter := _testCounter + 1;
          
          Insertion Sort
          N     | Steps
          ----- | -----
          10    | 31
          100   | 2554
          200   | 9859
          400   | 38719
          800   | 153439
          
          dFx's Insertion Sort
          N     | Steps
          ----- | -----
          10    | 29
          100   | 619
          200   | 1441
          400   | 3293
          800   | 7397
          

          This is interesting because you are applying the divide and conquer approach to insertion sort; thus, significantly reducing its speed complexity. Could we say that your code has speed complexity of 2*N*Log(2*N), while insertion sort has (N^2)/4?

          I did notice a bug where the first index of array does not get sorted.

           
          👍
          1

          Last edit: nothinrandom 2020-09-25
          • dFx

            dFx - 2020-09-25

            Well, the first index is not treated by the loop, as it starts at 1, but should be when we try to place the second. I will have a look later on to correct it.

            This may be something like divide, but to be honest, it is far from what quick sort could do. The problem is, we can't do recursive calls in codesys (afaik) and thus we have to maintain an explicit call stack and external parameters, which is yet more complexity and more overhead.

            In fact my approach, was to port an old program I did years ago, not knowing how to play with databases (in vb.net). I was browsing through sorted lists to recover some values, which is extremely slow as the list expand.
            Anyway, for any array bigger than 50 elements, I think we should really try to use a database, as this sorting is yet implemented and more efficient than what we can do.

            Have a good day.

             
            • dFx

              dFx - 2020-09-25

              @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;
              
               
              👍
              1

              Last edit: dFx 2020-09-25
              • nothinrandom - 2020-09-25

                @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;
                
                 
                👍
                1
  • dFx

    dFx - 2020-09-25

    Had a look at OSCAT basic, which is implementing quicksort in ARRAYSORT (REAL datatype only).
    it's 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 some measurements on a real PLC.
    Or maybe that's worthless reinventing what's already written down 😂

     

    Last edit: dFx 2020-09-25
  • Ingo

    Ingo - 2020-09-25

    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

     
    • nothinrandom - 2020-09-26

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

       
1 2 > >> (Page 1 of 2)

Log in to post a comment.