Bubble sort but, on a whole table

[userxyz]

Hey,

I have written a function in SCL for doing the bubble sort thing. The code is taken from wikipedia.

But, question I have is:

When you open excell, then you can select several colums and sort by a colum you want

So

I want to do the same in a PLC, is this possible ?

 

[Peter Nachtwey]

Simple.

Make the compare function use two compares if necessary. The first compare is done on the primary field. If the primary fields are the same then use the secondary field to break the tie.

A proper sort routine will have three functions. The first is the main sort function. This routine should never need to change. It just keeps track of indexes and the number of items to sort. The main sort routine calls two functions. The first is a compare function. This compare function will change depending on the UDT or data type. There will also be swap function that will swap two items or UDTs structures. The two helper functions should be where one does the addressing, comparing and swapping. If done right the two help routines can also be used for a shell sort or heap sort.

 

[userxyz]

simple

simple for you but I don't understand what you're explaining

Make the compare function use two compares if necessary. The first compare is done on the primary field. If the primary fields are the same then use the secondary field to break the tie.

A proper sort routine will have three functions. The first is the main sort function. This routine should never need to change. It just keeps track of indexes and the number of items to sort. The main sort routine calls two functions. The first is a compare function. This compare function will change depending on the UDT or data type. There will also be swap function that will swap two items or UDTs structures. The two helper functions should be where one does the addressing, comparing and swapping. If done right the two help routines can also be used for a shell sort or heap sort.

 

[kamenges]

Peter, I don't think that's what Combo is looking for. At least that isn't how I have used Excel ordering in the past. It sounds to me like he wants to sort on a single, selectable data list but wants to reorder related lists at the same time. He just need to make sure he swaps identical indices in all the array levels.

Combo, the only thing you really need to be careful of is the ordering of your data. You either need to maintain multiple parallel arrays or a single multi-dimensional array. As you scan one of the 'lists' (it doesn't matter which one) and you find a place that requires a swap you need to swap the same element indices in all the arrays (or all levels of the miltidimensional array).

Another way to handle that would be to maintain a separate list (array)that is your order list. This is simply an array of indices into the data array(s) that maintains the sort order. You just move those numbers around and leave the base data where it is.

Peter's response is correct, however. Build your fucntion modularly. It allows you to easily modify how the sort works without major changes to the nuts and bolts of the code.

Keith

 

[Pandiani]

Combo, just one side note...
Why do you want to use bubble sort. That is awful algorithm but usually very easy to implement. I think that insertion sort is better in most cases (although both have N^2 complexity).
Here's my implementation:

FUNCTION_BLOCK Sort_block

VAR_TEMP
  i : INT;
  j : INT;
  save_var : INT;
  temp_var : INT; 
END_VAR
VAR
  // Static Variables
  array_unsorted : ARRAY[0..9] OF INT;
  array_sorted : ARRAY [0..9] OF INT;
END_VAR
 
  // now creating array of integers in descending order
  FOR i:= 0 TO 9 BY 1 DO
	array_unsorted[i] := 9 - i;
	array_sorted[i] := array_unsorted[i]; 
	;
  END_FOR;
  // Now sort operation is performed
  
  FOR i:= 1 TO 9 BY 1 DO
	// Statement Section
	j := i - 1;
	temp_var := array_sorted[j];
	save_var := array_sorted[i];
  WHILE (j >= 0) AND (temp_var > save_var) DO 
	// Statement Section
	array_sorted[j + 1] := array_sorted[j];
	j := j -1;
	;
  END_WHILE;
	array_sorted[j + 1] := save_var;
	;
  END_FOR;
  ;
END_FUNCTION_BLOCK

For your problem, Peter's approach is very good. It provides modularity which is very good, especially in cases when you need to modify or change sort criteria.

Regards,
Pandiani

 

[userxyz]

Hmm

I understand your code...

But I still don't know how to sort...

I need sortation in a DB with an array of 150 DINT

And another DB with 150 strings has to follow the sortation of the DINT values...

How should I write this ?

Combo, just one side note...
Why do you want to use bubble sort. That is awful algorithm but usually very easy to implement. I think that insertion sort is better in most cases (although both have N^2 complexity).
Here's my implementation:

FUNCTION_BLOCK Sort_block
 
VAR_TEMP
i : INT;
j : INT;
save_var : INT;
temp_var : INT; 
END_VAR
VAR
// Static Variables
array_unsorted : ARRAY[0..9] OF INT;
array_sorted : ARRAY [0..9] OF INT;
END_VAR
 
// now creating array of integers in descending order
FOR i:= 0 TO 9 BY 1 DO
	array_unsorted[i] := 9 - i;
	array_sorted[i] := array_unsorted[i]; 
	;
END_FOR;
// Now sort operation is performed
 
FOR i:= 1 TO 9 BY 1 DO
	// Statement Section
	j := i - 1;
	temp_var := array_sorted[j];
	save_var := array_sorted[i];
WHILE (j >= 0) AND (temp_var > save_var) DO 
	// Statement Section
	array_sorted[j + 1] := array_sorted[j];
	j := j -1;
	;
END_WHILE;
	array_sorted[j + 1] := save_var;
	;
END_FOR;
;
END_FUNCTION_BLOCK

For your problem, Peter's approach is very good. It provides modularity which is very good, especially in cases when you need to modify or change sort criteria.

Regards,
Pandiani

 

[userxyz]

Can I use this ?

for i ← 0 to n-2 do
min ← i
for j ← (i + 1) to n-1 do
if A[j] < A[min]
min ← j
swap A[i] and A[min]



SWAP the DINT with this code and add a line like:

swap A[i] and A[min]

For swapping my strings too ?

 

[surferb]

Pete's reference to different sorting algorithms run O(N log N), versus a bubble sorts O(N^2). Vastly faster for large data sets, but probably doesn't matter, possibly even goes the other way with 150 elements - especially if the initial data is partially sorted.

But that doesn't matter. Your routine that swaps both arrays of values (string and number) should function properly. If it's too slow, consider ordering the indicies instead of moving the actual data around. That's what Pete was talking about using functions for.

 

[userxyz]

Code

FUNCTION FC123: VOID



// BUBBLESORT IN ARRAY



VAR_INPUT



TRIG: BOOL;



Data_In: ARRAY[1..10] OF INT; 



END_VAR 



VAR_OUTPUT



Data_Out: ARRAY[1..10] OF INT;



END_VAR 



VAR_IN_OUT



Flank_Mem: BOOL; 



END_VAR 



VAR_TEMP



i: INT;



v: BOOL;



j: INT;



Temp: INT;



Data: ARRAY[1..10] OF INT; 



Trig_Flank: BOOL;



END_VAR



 



BEGIN



Trig_Flank:= TRIG AND (NOT Flank_Mem); // Positieve flank op TRIG bit



IF Trig_Flank THEN



FOR i := 1 TO 10 DO



Data := Data_In ; // Data_In naar tijdelijke Data verzenden voor verwerking



END_FOR; 



i := 1;



v := True; 



WHILE i < 10 AND v = True DO



v := False;



j := 1;



WHILE j <= 10 - i DO



IF Data[j] > Data[j + 1] THEN



Temp := Data[j];



Data[j] := Data[j + 1];



Data[j + 1] := Temp;



v := True;



END_IF;



j := j + 1;



END_WHILE;



i := i + 1;



END_WHILE;







FOR i := 1 TO 10 DO // Gesorteerde tijdelijke Data verzenden naar Data_Out



Data_Out := Data ;



END_FOR;



END_IF; 



Flank_Mem:= TRIG; // Flank wegschrijven



END_FUNCTION

This is the code that I wrote long time ago, could have mistakes, but it works...

Anyone who believes this bubble sortation will work for sorting 2 columbs ?

Pete's reference to different sorting algorithms run O(N log N), versus a bubble sorts O(N^2). Vastly faster for large data sets, but probably doesn't matter, possibly even goes the other way with 150 elements - especially if the initial data is partially sorted.

But that doesn't matter. Your routine that swaps both arrays of values (string and number) should function properly. If it's too slow, consider ordering the indicies instead of moving the actual data around. That's what Pete was talking about using functions for.

 

[userxyz]

sortation

I trid with the bubble sort, doing bubble sort on 1 column and taken the column next to it in the sortation. When there is swapping on the first column, then the second one needs to follow,

But, I couldn't get it to work..

 

[userxyz]

Hey

It works in bubble sort now:

FUNCTION FC123: VOID



VAR_TEMP

swap: BOOL;

index: INT;

aux1: DINT;

aux2: STRING;

END_VAR



BEGIN

REPEAT

swap := FALSE;

FOR index := 200 TO 2 BY -1 DO

IF "BATCH LIST Buistype".Buistype[index-1] > "BATCH LIST Buistype".Buistype[index] THEN

aux1:="BATCH LIST Buistype".Buistype[index];

"BATCH LIST Buistype".Buistype[index] := "BATCH LIST Buistype".Buistype[index-1];

"BATCH LIST Buistype".Buistype[index-1] := aux1;

aux2:="BATCH LIST Record".Record[index];

"BATCH LIST Record".Record[index] := "BATCH LIST Record".Record[index-1];

"BATCH LIST Record".Record[index-1] := aux2;

swap := TRUE;

END_IF;

END_FOR;

UNTIL NOT swap

END_REPEAT;



END_FUNCTION

The only problem is that it's putting zero's before the sorted values if there were zeros in the table..., I don't like that Any ideas how to avoid this ?

 

[userxyz]

this works for 2 coulmns

[font=Arial][size=2]

FUNCTION FC123: VOID



VAR_TEMP

swap: BOOL; 

index: INT;

aux1: DINT;

aux2: STRING; 

END_VAR

 

BEGIN

REPEAT

swap := FALSE;

FOR index := 200 TO 2 BY -1 DO 

IF "BATCH LIST Buistype".Buistype[index-1] > "BATCH LIST Buistype".Buistype[index] THEN

aux1:="BATCH LIST Buistype".Buistype[index];

"BATCH LIST Buistype".Buistype[index] := "BATCH LIST Buistype".Buistype[index-1];

"BATCH LIST Buistype".Buistype[index-1] := aux1; 

aux2:="BATCH LIST Record".Record[index];

"BATCH LIST Record".Record[index] := "BATCH LIST Record".Record[index-1];

"BATCH LIST Record".Record[index-1] := aux2;

swap := TRUE;

END_IF;

END_FOR;

UNTIL NOT swap

END_REPEAT;



END_FUNCTION

[/size][/font]

This works,

Only problem= when having zeros in the table, it will put the zeros at the beginning, I don't want that, any ideas ?

 

[panic mode]

the code is absolutely identical, even if you have to handle several pieces of information. the only difference is that for multiple data blocks, you swap more data.

for example if you are sorting contacts by last name, you still compare one column such as LastName, but when swapping, you have to swap all info (first name, phone, fax, pager etc.).

 

[L D[AR2P#0.0]]

To put the zeros at the bottom of the table, first scan through the table and replace the zeros with a big number that will not be used, do the sort, then replace the big numbers with zeros:

e.g.

 

[userxyz]

Hey

I tried something like your code, but he doesn't accept it, I'm searching for the faults, do you see something that is not well written, this is my code:

IF SORTO_FLANK THEN
	FOR i:= 0 TO 500
		IF "ORDER_NUMMER".VARi[i]= 0 THEN
		   "ORDER_NUMMER".VARi[i]:= 50000;
		END_IF;						   
	END_FOR;
 REPEAT
 SWAP:= FALSE;
	FOR index:= 500 TO 1 BY -1 DO
	IF "ORDER_NUMMER".VARi[i - 1] > "ORDER_NUMMER".VARi[i] THEN
		aux1:= "ORDER_NUMMER".VARi[i];
		"ORDER_NUMMER".VARi[i]:= "ORDER_NUMMER".VARi[i - 1];
		"ORDER_NUMMER".VARi[i - 1]:= aux1;
	END_IF;
	END_FOR;
 UNTIL NOT swap;		   
 END_REPEAT;				   
	FOR i:= 0 TO 500
		IF "ORDER_NUMMER".VARi[i]= 50000 THEN
		   "ORDER_NUMMER".VARi[i]:= 0;
		END_IF;						   
	END_FOR;
END_IF;

To put the zeros at the bottom of the table, first scan through the table and replace the zeros with a big number that will not be used, do the sort, then replace the big numbers with zeros:

e.g.