Sorting Algorithms

eeng · Sep 18, 2016

Hi guys,

I'm using a Schneider Electric M340 PLC, I have a multi-dimensional array:
Array[1..10,1..10] of real. To give a little background. Each of those 10 arrays contains 6 parameters for a controller. They're run through a test and the score is recorded in the 7th element.

Now my problem is I need to sort those 10 arrays based on that 7th element.

More specifically I need to pluck the best two performing ones and write them to a new array set..

I've tried writing my own sorting algorithm although I only manage to take the first, best performing one as opposed to the top two.

This of course is programmed in ST.

Any advice would be appreciated,
Kind regards,
Max

Doug-P · Sep 18, 2016

I'm not familiar with ST but here's some pseudocode that might get you started.

Since from your description you don't really need to swap possibly ten locations, only to select the two highest values:

Code:

targetarray[10,7]
max1array[1,7]
max2array[1,7]
m1=0
m2=0

for I= 1 to 10
  if targetarray[I,7] > m1 then m1= targetarray[I,7]  \\ store highest score in m1
next
max1array[1] = targetarray[I]  \\ copy the high score data to another array

targetarray[I,7] = 0  \\ clear the highest score

for I= 1 to 10
  if targetarray[I,7] > m2 then m2 = targetarray[I,7]  \\ store next highest score in m2
next

max2array[1]=targetarray[I]  \\ copy 2nd high score data to another array

end

Saffa · Sep 19, 2016

Since your array is small, I'd take a look at "Bubble Sort".

It will take a few scans to sort but if you can wait 100ms or so for the result then all good. Bubble sort is not efficient but it is very simple to implement. Psuedocode on Wikipedia.

Once sorted then you can simply copy array element 1 and 2.

tragically1969 · Sep 19, 2016

eeng said:
Now my problem is I need to sort those 10 arrays based on that 7th element.

Can you expand on that a little ? What is the seventh element, how do you mean sort on that ?

CapinWinky · Sep 19, 2016

Quick tip on the bubble sort is that you run through less and less of the array each time. First time you do 1..10, then just 1..9 because the largest/smallest element always runs down to the end. In your case you can push the smallest elements to the end and only run the sort twice to get your final two in the last two positions.

Faster might be a simple

IF([i,7] < Result1) THEN
//record first place
ELSIF(i,7 < Result2) THEN
//record second place
END_IF

robertmee · Sep 19, 2016

tragically1969 said:
Can you expand on that a little ? What is the seventh element, how do you mean sort on that ?

What he means is that the 7th element of each index of his 10 x 10 array is the sort criteria. Each 10 element array he's only using 6 elements, where the 7th element is the score of the values in 1 to 6. So, the 7th element is his sort criteria. For example:

Array[1] = 1,2,3,4,5,6,50,0,0,0
Array[2] = 5,4,3,2,1,6,51,0,0,0
Array[3] = 4,4,4,4,4,4,55,0,0,0
Array[4] = 1,1,1,1,1,1,34,0,0,0
etc

After his manipulation he wants two new arrays

New_Array[1] = 4,4,4,4,4,4,55,0,0,0 (Highest score of 55)
New_Array[2] = 5,4,3,2,1,6,51,0,0,0 (2nd Highest Score of 51)

The 1st psuedo lays it out pretty well....Doesn't need to sort or do nested loops. Just copy the entire 10x10 into a temp array....On the first FOR-NEXT 1 to 10, find the highest score and move it to New_Array[1]. Then CLEAR out that entire row in the temp array. Rerun the same FOR-NEXT 1 to 10, which finds the 2nd highest since the 1st highest was cleared out. Copy that to New_Array[2]. Done and done.

Lare · Sep 19, 2016

On Unity I would maybe use search max array function for this.

First copy your 7th elements from original array to new 10 point array. (array 1..10 of int/real/word]

Then search from this highest value with max_* array command. Search function will give location of highest array with number 1..10.

Now you know highest array location number (place X.) -> copy from original 10*10 array all numbers to new location.

After 1st search, copy zero to highest array place on 1..10 array (place X)

Now you can search again from array 1..10 highest number. (= Highest numer on second search is you 2nd biggest number. Place Y)

copy from 10*10 array...

zero location Y on 1..10 array.

seach again with max_array, now you find 3th biggest number.

etc..

You can do this all on one plc cycle.

Peter Nachtwey · Sep 19, 2016

eeng said:
Hi guys,

I'm using a Schneider Electric M340 PLC, I have a multi-dimensional array:
Array[1..10,1..10] of real. To give a little background. Each of those 10 arrays contains 6 parameters for a controller. They're run through a test and the score is recorded in the 7th element.

Now my problem is I need to sort those 10 arrays based on that 7th element.

So elements 8, 9 and 10 are empty?

More specifically I need to pluck the best two performing ones and write them to a new array set..

First you need a swap function that will swap two aways. This usually involves copying array I to array temp, array j to array I and then copy array temp to array j.

I've tried writing my own sorting algorithm although I only manage to take the first, best performing one as opposed to the top two.

Like people said, use a bubble sort BUT only sort go through the array twice because that is all that is required to put the best two arrays at the beginning or end depending on your need. You could sort the whole array but that would be a waste of time.

This of course is programmed in ST.

Any advice would be appreciated,
Kind regards,
Max

I would look on line. There are plenty of examples.

Another option, if new arrays need to be added one at time I would just sort the new array in the list. The code would be simpler and faster. Look for insertion sort but you only need to sort one item.

There are "faster" sorting algorithms out there but you application is simple and small. The most important thing is to "sort in place". The bubble sort does that. Heap sort and quick sort use a stack that can over flow and crash. Keep it simple.

shooter · Sep 19, 2016

sorting is not needed, only find the highest and the one that is just below.
if sort is needed, asimple bubble is fine

eeng · Sep 20, 2016

robertmee said:
Then CLEAR out that entire row in the temp array.

I think there's my problem. When I get the first high score, I clear that value but in the target array and then get it to search through again.

Note: The high score...is the lowest score (error)
I think my main problem is my limited understanding of the way these loops are executed. I have probably structured the FOR loops incorrectly. I understand the concept...just can't put it into words haha...

What do you guys think about this:
http://users.isr.ist.utl.pt/~jag/aulas/api14/docs/PLC_2_Unity_Reference_Standard_Block_Library.pdf

Page 103-104. Apparently Unity Pro does have a sort command.

If I sorted the scores, could I just then run a loop:

For i:=a to b DO
IF TargetArray[7]=TempScore[1] THEN
FOR x:=a to b DO
TopArray1[x]:=TargetArray[x]

then repeat for TempScore2

That's my other problem...keeping the scores connected to their respective parameter sets.

Thanks for all the replies.

Jeebs · Sep 20, 2016

Code:

k := 1
l := 0

For i = 2 to 10 Do      // 2 to 10 cause you already have 1 as highest atm
   If TargetArray[i].7 > TargetArray[k].7 Then
      l := k;              // If value is higher, set current highest to second highest
      k := i;              // Then set new highest
   Else If l == 0 Then     // This is to avoid access violations since TargetArray[0] doesn't exist
      l := i;
   Else If TargetArray[i].7 > TargetArray[l].7 Then
      l := i;
   End if;
End;

TopArray[1] := TargetArray[k];
TopArray[2] := TargetArray[l];

I'm guessing this should work. Guessing/hoping.

For 2 identical max values, both will be selected. For 3 identical max values, only the first 2.
For 2 or more identical max-1 values, only the first one detected will be selected.

eeng · Sep 20, 2016

Thanks for that Jeebs, I will give it a go soon. I'm guessing that will only copy the scores over to TopArray[1] and TopArray[2]? and not the parameters as well?

I'll post my code when I get home.

I should have mentioned, this is for a genetic algorithm..so those two top parameter sets will be used as parents to generate a new round of individuals.

Saffa · Sep 20, 2016

I would store the parameters as well, or at least an index to them in relation to the original array, if it won't change during whatever your next step is.

eeng · Sep 20, 2016

Yeah I have stored them in a "temp" array set. Although like I mentioned earlier I'm pretty sure my code is structured wrong so things aren't executing properly/correct order. I'll post the code...I'm sure you guys will spot the obvious errors that I don't see.

Jeebs · Sep 20, 2016

Not sure about the platform you're using, so was guessing/used Pascal-based syntax. The last 2 lines are meant to copy the entire 10 item array, thus with parameters, into the TopArray[x].
In ControlLogix it would be:
COP(TargetArray[k],TopArray[1],1);
COP(TargetArray[l],TopArray[2],1);

Sorting Algorithms

eeng

Member

Doug-P

Member

Saffa

Member

tragically1969

Member

CapinWinky

Member

robertmee

Lifetime Supporting Member

Lare

Member

Peter Nachtwey

Member

shooter

Member

eeng

Member

Jeebs

Member

eeng

Member

Saffa

Member

eeng

Member

Jeebs

Member

Similar Topics