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
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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.
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
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.
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.
The Value[e] := temp[1] should be Value[y] := temp[1]; this is a temporary value
X will just run to the value max (point 3 will explain what max means). No need to compare it with anything
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.
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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)
(*Purpose: Run an optimized version of bubble sort with specified order* Author: NothinRandom* v1.0 September 16, 2020* Note:*)FUNCTIONnumBubbleSort:BOOLVAR_INPUTpbBuffer:POINTERTOBYTE;//pointertobufferudiElements:UDINT;//arraylengthuiDataType:UINT;//datatype: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;//defaultascendingEND_VARVAR_uiDataSize:UINT;//elementsize_udiIndex1:UDINT;//loopindex_udiIndex2:UDINT;//loopindex_bSwapped:BOOL;//optimization_abTemp:ARRAY[1..8]OFBYTE;//storetempvalue_pbTemp:POINTERTOBYTE;//pointertotemp_psiElement1:POINTERTOSINT;//pointeroperator_psiElement2:POINTERTOSINT;//pointeroperator_pbElement1:POINTERTOBYTE;//pointeroperator_pbElement2:POINTERTOBYTE;//pointeroperator_piElement1:POINTERTOINT;//pointeroperator_piElement2:POINTERTOINT;//pointeroperator_puiElement1:POINTERTOUINT;//pointeroperator_puiElement2:POINTERTOUINT;//pointeroperator_pdiElement1:POINTERTODINT;//pointeroperator_pdiElement2:POINTERTODINT;//pointeroperator_pudiElement1:POINTERTOUDINT;//pointeroperator_pudiElement2:POINTERTOUDINT;//pointeroperator_pliElement1:POINTERTOLINT;//pointeroperator_pliElement2:POINTERTOLINT;//pointeroperator_puliElement1:POINTERTOULINT;//pointeroperator_puliElement2:POINTERTOULINT;//pointeroperator_prElement1:POINTERTOREAL;//pointeroperator_prElement2:POINTERTOREAL;//pointeroperator_plrElement1:POINTERTOLREAL;//pointeroperator_plrElement2:POINTERTOLREAL;//pointeroperatorEND_VAR===============================================================================CASEuiDataTypeOF1://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;ELSERETURN;END_CASE//getreferencepointer_pbTemp:=ADR(_abTemp);FOR_udiIndex1:=1TOudiElements-1DO_bSwapped:=FALSE;FOR_udiIndex2:=1TOudiElements-_udiIndex1DOCASEuiDataTypeOF1://SINT_psiElement2:=_psiElement1+_uiDataSize;IFNOT(bDescending)THEN_bSwapped:=_psiElement1^>_psiElement2^;ELSE_bSwapped:=_psiElement1^<_psiElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_pbElement1^>_pbElement2^;ELSE_bSwapped:=_pbElement1^<_pbElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_piElement1^>_piElement2^;ELSE_bSwapped:=_piElement1^<_piElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_puiElement1^>_puiElement2^;ELSE_bSwapped:=_puiElement1^<_puiElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_pdiElement1^>_pdiElement2^;ELSE_bSwapped:=_pdiElement1^<_pdiElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_pudiElement1^>_pudiElement2^;ELSE_bSwapped:=_pudiElement1^>_pudiElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_pliElement1^>_pliElement2^;ELSE_bSwapped:=_pliElement1^<_pliElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_puliElement1^>_puliElement2^;ELSE_bSwapped:=_puliElement1^<_puliElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_prElement1^>_prElement2^;ELSE_bSwapped:=_prElement1^<_prElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(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;IFNOT(bDescending)THEN_bSwapped:=_plrElement1^>_plrElement2^;ELSE_bSwapped:=_plrElement1^<_plrElement2^;END_IFIF(_bSwapped)THEN//storetempvalue,andswapSysMemCpy(pDest:=_pbTemp,pSrc:=_plrElement2,udiCount:=_uiDataSize);_plrElement2^:=_plrElement1^;SysMemCpy(pDest:=_plrElement1,pSrc:=_pbTemp,udiCount:=_uiDataSize);END_IF_plrElement1:=_plrElement1+_uiDataSize;END_CASEEND_FOR//exitifalreadysortedIF(NOT_bSwapped)THENEXIT;END_IFCASEuiDataTypeOF1://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_CASEEND_FORnumBubbleSort:=TRUE;
Last edit: nothinrandom 2020-09-24
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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.
(*Purpose: Run an optimized version of insertion sort with specified order* Author: NothinRandom* v1.0 September 16, 2020* Note:*)FUNCTIONnumInsertSort:BOOLVAR_INPUTpbBuffer:POINTERTOBYTE;//pointertobufferdiElements:DINT;//arraylengthuiDataType:UINT;//datatype:sint(1),usint/byte(2),int(3),uint(4),dint(5),udint(6),lint(7),ulint(8),real(9),lreal(10)bOrder:BOOL:=FALSE;//defaultascendingEND_VARVAR_uiDataSize:UINT;//elementsize_udiIndex1:UDINT;//loopindex_udiIndex2:UDINT;//loopindex_bSwapped:BOOL;//optimization_abTemp:ARRAY[1..8]OFBYTE;//storetempvalue_pbTemp:POINTERTOBYTE;//pointertotemp_psiElement1:POINTERTOSINT;//pointeroperator_psiElement2:POINTERTOSINT;//pointeroperator_pbElement1:POINTERTOBYTE;//pointeroperator_pbElement2:POINTERTOBYTE;//pointeroperator_piElement1:POINTERTOINT;//pointeroperator_piElement2:POINTERTOINT;//pointeroperator_puiElement1:POINTERTOUINT;//pointeroperator_puiElement2:POINTERTOUINT;//pointeroperator_pdiElement1:POINTERTODINT;//pointeroperator_pdiElement2:POINTERTODINT;//pointeroperator_pudiElement1:POINTERTOUDINT;//pointeroperator_pudiElement2:POINTERTOUDINT;//pointeroperator_pliElement1:POINTERTOLINT;//pointeroperator_pliElement2:POINTERTOLINT;//pointeroperator_puliElement1:POINTERTOULINT;//pointeroperator_puliElement2:POINTERTOULINT;//pointeroperator_prElement1:POINTERTOREAL;//pointeroperator_prElement2:POINTERTOREAL;//pointeroperator_plrElement1:POINTERTOLREAL;//pointeroperator_plrElement2:POINTERTOLREAL;//pointeroperatorEND_VAR===============================================================================CASEuiDataTypeOF1,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;ELSERETURN;END_CASE//getreferencepointer_pbTemp:=ADR(_abTemp);FOR_diIndex1:=1TOdiElements-1DO_testCounter:=_testCounter+1;//getkeySysMemCpy(pDest:=_pbTemp,pSrc:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex1),udiCount:=_uiDataSize);_diIndex2:=TO_DINT(_diIndex1-1);CASEuiDataTypeOF1://SINT_psiElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_psiElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_psiElement1^>_psiElement2^;ELSE_bSwapped:=_psiElement1^<_psiElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_psiElement1+_uiDataSize,pSrc:=_psiElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE2://USINT/BYTE_pbElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_pbElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_pbElement1^>_pbElement2^;ELSE_bSwapped:=_pbElement1^<_pbElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_pbElement1+_uiDataSize,pSrc:=_pbElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE3://INT_piElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_piElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_piElement1^>_piElement2^;ELSE_bSwapped:=_piElement1^<_piElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_piElement1+_uiDataSize,pSrc:=_piElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;_testCounter:=_testCounter+1;END_WHILE4://UINT_puiElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_puiElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_puiElement1^>_puiElement2^;ELSE_bSwapped:=_puiElement1^<_puiElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_puiElement1+_uiDataSize,pSrc:=_puiElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE5://DINT_pdiElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_pdiElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_pdiElement1^>_pdiElement2^;ELSE_bSwapped:=_pdiElement1^<_pdiElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_pdiElement1+_uiDataSize,pSrc:=_pdiElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE6://UDINT_pudiElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_pudiElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_pudiElement1^>_pudiElement2^;ELSE_bSwapped:=_pudiElement1^<_pudiElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_pudiElement1+_uiDataSize,pSrc:=_pudiElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE7://LINT_pliElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_pliElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_pliElement1^>_pliElement2^;ELSE_bSwapped:=_pliElement1^<_pliElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_pliElement1+_uiDataSize,pSrc:=_pliElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE8://ULINT_puliElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_puliElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_puliElement1^>_puliElement2^;ELSE_bSwapped:=_puliElement1^<_puliElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_puliElement1+_uiDataSize,pSrc:=_puliElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE9://REAL_prElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_prElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_prElement1^>_prElement2^;ELSE_bSwapped:=_prElement1^<_prElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_prElement1+_uiDataSize,pSrc:=_prElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILE10://LREAL_plrElement2:=_pbTemp;WHILE(_diIndex2>=0)DO_plrElement1:=pbBuffer+TO_UDINT(_uiDataSize*_diIndex2);//ascending/descendingIFNOT(bOrder)THEN_bSwapped:=_plrElement1^>_plrElement2^;ELSE_bSwapped:=_plrElement1^<_plrElement2^;END_IFIF(NOT_bSwapped)THENEXIT;END_IF//next=currentSysMemCpy(pDest:=_plrElement1+_uiDataSize,pSrc:=_plrElement1,udiCount:=_uiDataSize);_diIndex2:=_diIndex2-1;END_WHILEEND_CASE//setkeySysMemCpy(pDest:=pbBuffer+_uiDataSize*(TO_UDINT(_diIndex2)+1),pSrc:=_pbTemp,udiCount:=_uiDataSize);END_FORnumInsertSort:=TRUE;
👍
1
Last edit: nothinrandom 2020-09-24
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
@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)."
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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).
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
@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?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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 (EXTENDS) 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).
OPEN POINT
Since the function Sort uses an internal array of byte to be able to perform a variable swap, if your data type exceed the length of the array, the Sort method will return FALSE and your array will not be sorted. Maybe we should also pass as parameter the location of the temp variable to ensure that the swap will always be possible?
Or should we also add a method "Swap" which also need to be overriden?
We also can call the operator __NEW() with the needed byte count...
What are your thougt about it?
Back to the code
See code below (I have attached 2 FB's in PLCopenXML format):
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_INPUTEND_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*)METHODABSTRACTCompare:DINTVAR_INPUTa:PVOID;b:PVOID;END_VAR
// No code here since it is an abstract method !!!
Sort method:
METHOD FINAL Sort : BOOLVAR_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 ascendingEND_VARVAR _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
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_SortVAR_INPUTEND_VARVAR_OUTPUTEND_VARVAREND_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*)METHODCompare:DINTVAR_INPUTa:PVOID;b:PVOID;END_VARVAR_a:REAL;//_b:REAL;END_VAR
About the MEMCMP/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 😋
Last edit: gised-link 2021-11-25
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
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
more posts ...
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
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.
Then to call it:
This was quickly thrown together so no guarantees but hope it at least gets you started.
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
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
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
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.
Hope this works for you. If not, please let me know
Related
Talk.ru: 1
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.
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
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_
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)
To sort SINT array in ascending order:
To sort SINT array in descending order:
To sort real array in ascending order:
Last edit: nothinrandom 2020-09-24
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.
To sort SINT array in ascending order:
To sort SINT array in descending order:
To sort real array in ascending order:
Last edit: nothinrandom 2020-09-24
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.
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.
Last edit: nothinrandom 2020-09-17
@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)."
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.
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?
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).
Last edit: dFx 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.
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.
Last edit: nothinrandom 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.
@nothinrandom
Fixed code with some cleanup.
Feel free to add it to your base.
Last edit: dFx 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:
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
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
@Ingo, I tried using datatype ANY at first. However, we're not allowed to have something like
ARRAY[1..10] OF ANY_NUM
orPOINTER TO ARRAY[1..10] OF ANY_NUM
, so it can only beANY_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?You're right. I forgot 😉
A workaround for this can be:
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 (EXTENDS) 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).
OPEN POINT
Since the function Sort uses an internal array of byte to be able to perform a variable swap, if your data type exceed the length of the array, the Sort method will return FALSE and your array will not be sorted. Maybe we should also pass as parameter the location of the temp variable to ensure that the swap will always be possible?
Or should we also add a method "Swap" which also need to be overriden?
We also can call the operator __NEW() with the needed byte count...
What are your thougt about it?
Back to the code
See code below (I have attached 2 FB's in PLCopenXML format):
The Abstract function block FB_Sort with abstract method Compare and final method Sort:
Compare method:
// No code here since it is an abstract method !!!
Sort method:
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):
// Leave the body empty
Then, simply override the Compare method:
And I use the code like it somewhere inside my project:
Last edit: gised-link 2021-11-24
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 stored 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 👍
Edit : Typo
Last edit: dFx 2021-11-25
About the MEMCMP/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 😋
Last edit: gised-link 2021-11-25
(for the future me: DO NOT SPAM THE POST BUTTON)
Last edit: gised-link 2021-11-25