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:
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_NUMorPOINTER TO ARRAY[1..10] OF ANY_NUM, so it can only beANY_NUMinside VAR_INPUT. I am not sure how we could provide sorting in this scenario. Is it possible to move this thread into Engineering?