Help with sorting block

[moistcat]

Hi All,

Wondering if I could get a hand with why my bubble sort isn't working.
I need to take 3 REAL inputs, and 3 BOOL enable inputs.
Then return the index of the largest enabled real:
ENA, INPUT
TRUE, 33.5
FALSE, 80.0
TRUE, 26.8
Return: 0 (zero based index of largest true value)

ENA, INPUT
FALSE, 33.5
FALSE, 80.0
TRUE, 26.8
Return: 2 (zero based index of largest true value)

Any help would be greatly appreciated, Im also happy to take a different approach as I feel like i'm massively overthinking this...

Attached screenshots should be returning LargestIs1 = TRUE

 

[L33er]

Css!

 

[JTCat]

Your bits are very destructive. The state of the logic is hard to follow but without seeing the rest of it I'll guess that if the output isn't working then the routine isn't being scanned by the main program?

 

[drbitboy]

mov input1 valout xic ena1 ote bitout



bst xio bitout nxb xic ena2 grt input2 valout bnd bst xic ena2 ote bitout nxb mov input2 valout bnd



bst xio bitout nxb xic ena3 grt input3 valout bnd bst xic ena3 ote bitout nxb mov input3 valout bnd

​

KISS?

 

[moistcat]

Thanks everyone,
@drbitboy, I'm not quite sure this returns the largest enabled value. Did you intend for the bitout's to be bitout1,2,3 etc ?

 

[moistcat]

Ok this seems to be working, and will scale better if required in future.
Happy to be shown a better way to do it, this seems v convoluted for what it is.

/* 
 UTIL_FindLargest

 This function will take a number of input values, and enable flags.
 Return the index of the largest 'Enabled' value.
 
 - All index's are zero based
 - if multiple inputs are the same and enabled, output will be highest index number.

*/

// init values
input[0] := Num0;
input[1] := Num1;
input[2] := Num2;
index[0]:=0;
index[1]:=1;
index[2]:=2;
ena[0]:=Ena0;
ena[1]:=Ena1;
ena[2]:=Ena2;
largestEna[0]:=0;
largestEna[1]:=0;
largestEna[2]:=0;

// bubble sort input array
REPEAT swap := 0;
	FOR i:=2 TO 1 BY -1 DO
    	IF input[i-1] > input[i] THEN
    		// swap the 2 numbers
	        tempReal:=input[i];
	        input[i] :=input[i-1];
	        input[i-1] :=tempReal;
	        swap:=1;

			// keep track of the input number index so we know where it was originally
			tempInt:=index[i];
			index[i]:=index[i-1];
			index[i-1]:= tempInt;
    	END_IF;
	END_FOR;
UNTIL NOT swap END_REPEAT;

// print the sorted values for debug
Index0:=index[0]; // smallest
Index1:=index[1];
Index2:=index[2]; // largest

// search list for highest enabled value
exitFlag:=0;
FOR j:=2 TO 0 BY -1 DO
	FOR i:=0 TO 2 DO
	    IF index[j] = i & ena[i] THEN
			largestEna[i] :=1;
			exitFlag:=1;
			exit;
	    END_IF;
	END_FOR;
	if exitFlag then 
		exit;
	end_if;
END_FOR;

Input0IsLargest := largestEna[0];
Input1IsLargest := largestEna[1];
Input2IsLargest := largestEna[2];

 

[drbitboy]

Thanks everyone,
@drbitboy, I'm not quite sure this returns the largest enabled value. Did you intend for the bitout's to be bitout1,2,3 etc ?

No. bitout is a second output of the function; it is 0 if all 3 of the BOOL enable inputs are 0.

This can be done with a one-pass approach in linear time; there is no need to sort.

Ah, I just re-read the problem statement; you want the index of the largest enabled value; my algorithm gives the largest value instead of the index.

largest_enabled = False;
largest_enabled_index = -1;
largest = 0.0;

IF Ena0 THEN
    IF Inp0 > largest OR NOT largest_enabled THEN
        largest_enabled = True;
        largest_enabled_index = 0;
        largest = Inp0;
    END_IF
END_IF;

IF Ena1 THEN
    IF Inp1 > largest OR NOT largest_enabled THEN
        largest_enabled = True;
        largest_enabled_index = 1;
        largest = Inp1;
    END_IF
END_IF;

IF Ena2 THEN
    IF Inp2 > largest OR NOT largest_enabled THEN
        largest_enabled = True;
        largest_enabled_index = 2;
        largest = Inp2;
    END_IF
END_IF;

I don't see a point in doing a loop for three items, but it could be done that way.

 

[drbitboy]

Ok this seems to be working, and will scale better if required in future.

Considering that it does two O(N^2) operations, one of which is not required, I would not say it scales well at all, unless "scaling" applies to coding i.e. for extending it to more values.

Happy to be shown a better way to do it, this seems v convoluted for what it is.

Here is an algorithm that scales O(N) for both re-coding and execution:

inp[0] := Num0;

ena[0] := Ena0;

inp[1] := Num1;

ena[1] := Ena1;

...

inp[count-1] := Num<count>;

ena[count-1] := Ena<count>;



hi_index := 0



FOR j=0 to (count-1) TO 0 DO

    IF ena[j] AND ( hi_index = 0 OR ( hi_index > 0 AND inp[hi_index-1] <= inp[j] ) ) THEN

        hi_index = j + 1;

    END_IF;

END_FOR;

​

Alternate loop and IF logic:

FOR j=(count-1) TO 0 BY -1 DO

    IF ena[j] AND ( hi_index = 0 OR ( hi_index > 0 AND inp[hi_index-1] < inp[j] ) ) THEN

        hi_index = j + 1;

    END_IF;

END_FOR;

​

N.B. Both FOR/IF constructs ensure higher index breaks ties.

 

[plvlce]

Considering that it does two O(N^2) operations, one of which is not required, I would not say it does not scale well at all, unless "scaling" applies to coding i.e. for extending it to more values.

Is the double negative intentional?

 

[drbitboy]

Is the double negative intentional?

:thanks:

 

[moistcat]

Ahh thanks again DrBitBoy! Much more straightforward.

I did mean it would better scale with adding more inputs, but agree that it is silly to sort the whole list when not required.