Alphabetical Sort in RSLogix 5000

I have been presented with a programming challenge and hope that some of the Forum members may have some insight or experience to share.

A customer will have a long array of text strings in his ControlLogix controller. These will be part of a UDT which includes a number that points to an offset in another array of data. Essentially it's a long list of named numbers, which are themselves not in any sequence (just the order in which they were entered.)

My challenge is that I need to display them in RSView ME.. in alphabetical order. And then I need the customer to be able to type in a name and find it in the list.

Probably this is a trivial matter in PC programming, but I'm not a PC programmer and this is a Logix controller.

Does anyone on the Forum have some insight into the science and art of alphabetical sorting ? I'm off to begin with Google, of course, but figured I'd look here too.

My first inclination is to say... "Bubble Sort", but then, how do you determine the ASCII code of the letters?

If you can, then you need to run several iterations (actually, many, 26 for characters, then ?-iterations for... space, dash, ampersand,...???) through the character count in each string.

I believe you can straight compare the ASCII Characters, and they are weighted alphabetically. Use a couple of Indexes, step through the individual parts of the strings to be compared, run those through a do while loop.

I'll fool with this when I've got emulate in front of me.

1. As CroCop mentioned, one glance at an ASCII table shows that '0' < '9' < 'A' < 'Z' < 'a' < 'z'. The individual characters will compare nicely.

2. Unfortunately since the packing of the characters starts with the lowest byte of a 32 bit word you can't group them and do DINT compares.

3. The time for bubble sorts grows incredibly fast as the number of items increases. An insertion sort is marginally better. Possibly an in-place Quicksort. These could be written as to execute over many program scans (assuming the table is locked for that time). I've done a multi-scan bubble sort in RSLogix 500 ladder but that was for a fairly small table.

Does ME support VB scripting?
If it's only for display, VB can bang out an alphabetical sort much easier then a PLC.

Bernie has the right idea about the in place quicksort.

I didn't know one could compare characters on a Control Logix so I hadn't replied, but since someone said it is possible I will add my $2 worth.
Ken, you want to sort indexes or pointers to the beginning of strings. Move the indexes or pointers. You do not want to move the strings themselves.
It takes only a little more effort to do a quick sort than a bubble sort but the speed difference is tremendous as N gets large.
Quiz, at what value of N does it pay to do a quick sort?
Since this forum has conquered the toggle, traffic lights and and other trivial problems I think this is a good problem.
Ken, but I am surprised you didn't provide a range for N so we can make the decision about which sort to use, bubble or quick sort. N is geek speak for the number of items to sort.

A sorting program usually comes in two parts. The compare routine and the sort routine itself. The compare routine compares to items and returns a -1,0, or 1 depending on whether the comparison is less than, equal or greater than. The sort routine uses this compare routine to determine the sorting order. C++ and C is smart enough to compile small routines so they are coded in-line so many comparisons are not actually compiled as separate routines.

First Ken needs a compare routine just to make sure it is possible. This is required no matter which sort algorithm he decides to use. After that the in-place quick sort or bubble sort ( yuk ) should be easy.

Optimal sorting and searching are import tools to have in you tool box.

This is a controller-managed recipe system. The user wants to be able to input a recipe name instead of a recipe number, and then look up the recipe by name instead of number. I anticipate attaching numbers, too, so I can use them as pointers to find the actual recipe data sets.

The customer couldn't really tell me what sort of names he was looking for; maybe "Podunk 14mm April 12", which I need to be able to sort versus "Charlestown June 7mm".

This originally started out as a 500 recipe system, and we tried to do it in RSView ME, but when the requirement for sort-by-name came up, and the number of recipes balooned to 5000 and we were enjoined not to use VB or VBA or a computer with a rotating hard drive.

So here I am, learning about bubble sorts and quick sorts and the Postman's Sort.

I was hoping there was some sort of hash or checksum method I could use to convert the string to a value, and compare the values. I haven't discovered something like that which will work.

Ken, I'm thinking that maybe a good approach would be to not sort at all.

Are you familiar with a b-tree or binary search tree? Its a common form of data-base indexing scheme which keeps pointers to data entries in an appropriate order as the data is entered so that the data base never needs sorting. In fact, I believe that the symbol/comment database of Logix 500 uses a b-tree.

Anyways, I'm thinking that something similar could be implemented in ST. The CLX doesn't have dynamic memory allocation which would make it much easier, but I think that if we had a couple of UDT arrays we could pull it off. The tree array would contain N+1 (i think) indexing UDTs where N is the number of entries to be indexed. Each UDT in the index array would contain several pointers - a pointer to the matching string (if there was a match) and a right and left child pointer which actually just contain the next array index we look at for a match. If the search string > current string, branch right, or branch left if its less than. New entries are placed into the array at teh first empty slot but tree insertions at the appropriate place (sorted) is done by simply by resetting the child and parent pointers. Unused locations in the array could be kept as a linked list. I'll have to give this some more thought, but offhand I don't see any reason why it can't be done in ST if the UDTs are set up right. Then viola, a no-sort index which is sorted by default.

One major drawback is that binary trees are a fairly advanced concept for most programmers. While not too dificult to code if you get the concept, the concept itself will likely be way beyond any PLC guys at the customer's facility. Bubba will just sit and scratch his head (or something else).

Here's a decent overview of different sorting algorithims:

http://people.cs.uct.ac.za/~bmerry/manual/algorithms/sorting.html

Personally though, I'd recommend reading chapter 12 of the Common Procedures Programming Manual (Publication #1756-PM001H-EN-P) in Rockwell's Literature Library. It's on how to deal with ASCII.

You could create a custom data type for the recipie data with one of the elements being a string that contains the name. Then use the functions described in the above document to find the data set your user is looking for.

This would eliminate the need to bother with sorting and 're-inventing the wheel' so to speak.

User defined data Types are one of the reasons I've grown a fondness for ControlLogix. They look a bit messy in ladder when refrencing an array of them, but can be damn handy if you understand them.

N=5000 is not trivial. A bubble sort will not do.

N = 5000 names requires the best sorting algorithm. Again, as Bernie suggested, the quick sort is required. The in-place version would be best.

Ken has mentioned hashing. This is a good way to go if the goal is not to sort but to find a recipe quickly. The trick is to find a way of making unique hash keys.

What is the main goal? When hashing is mentioned, that changes things completely. Now you need a hashing algorithm, CRCs are good for that but time consuming. Hashing is not a trivial subject either.

Seriously... don't bother with the sort. I just glanced over chapter 12 of the Rockwell publication I cited above and I think it's the answer you're looking for since you are doing this all in the controller.

The example they use throughout the chapter is for an airport baggage sorter. They show how to decode a barcode. Create a user defined data type to store the barcode and sorting info in, and then lookup and retrieve the data from the user defined data type. I believe the magic instruction is FSC (file search and compare).

The part that pertains to you is creating the data type and then searching it to retrieve the data.

Ken's main problem is he wants to display the string portion of the data in alphabetical order. I don't think the display is smart enough to show an unordered list6 of strings alphabetically. Therefore the arrray of strings (actually the array of UDT's of which they are a part) have to be sorted. The two main obstacles:

1. There is no built in string compare function that I know of. There are other string operations but not that. So a subroutine will have to be written which receives two strings and returns the -1, 0, 1 judgement. Look up 'STRCMP' and 'implementation' in Google. I find the compares in 'C' the most readable. That will give an outline on implementing the compare in whichever language can be used in the processor. The lower the level the better sppedwise.

2. The next part is a toughie. the Quicksort method of sorting depends on recursive subroutines. I don't believe the routines in the PLC are of that type.

(A recursive subroutine can, in its execution, call itself with a smaller portion of the problem to solve. An example is the factorial routine. It recieves a number 'n' as an argument. If 'n' is 1 it returns '1' as the answer, else it calls factorial with 'n-1' as an argument and multiplies whatever returns by 'n' then returns the product as an answer. This could possibly work on a PLC until the number of nested calls blows through the PLC's limit.)

The Quicksort works by taking the space to be sorted then, if the space has more than 1 item, picking one of the keys, then 'partitioning' the space into 3 sections, all those entries whose keys are LESS THAN the chosen key, the entry with the chosen key, and all the rest whose keys are MORE THAN the chosen key. (This assumes the keys are unique.) Then 'partition' is called twice, once for he LESS THAN and once for the GREATER THAN sections. This keeps repeating all the way down until all the subsection are completely 'partioned' which means the whole array is sorted. It's one of the quickest sorts.

You may have to implement a sort like the insertion sort which doesn't use recursion but on 5000 entries it's gonna take a while. This is why I suggested setting the sort up to implement over a nuymber of scans during which the array is locked from any further entries.


Are you sure there's no Knowledgebase articles on this type of sorting?

bernie_carlton said:

1. There is no built in string compare function that I know of. There are other string operations but not that. So a subroutine will have to be written which receives two strings and returns the -1, 0, 1 judgement.

Click to expand...

All of the CLX compare instructions will accept string operands, including the FSC. Maybe one day the SRT instruction will as well.

This is how I would attack the problem...

Sort the data as it is entered, but only do one compare per scan to keep it simple at first.

Accept the input to a NewRecipe data file of type (your UDT). You'll also have an array of 500 of those UDTs called Recipe or something like that.

When an entry is made, latch a bit "NEW_RECIPE" and pop up a "SORTING" message.

Do a One shot off of it to reset the index N of your compare routine and reset the "COMP_DN" (compare done) bit.

If NEW_RECIPE and NOT COMP_DN then if NewRecipe.name > Recipe(N).name then OTL COMP_DN.

'Make sense? Scary Huh?

XIC NEW_RECIPE----XIC COMP_DN---COPY Source: Recipe N Dest: Recipe N+1 Length 499-N*----(branch)-----MOV NewRecipe Dest Recipe(N)------(branch)----OTU NEW_RECIPE

If NEW RECIPE then N=N+1

'Still following this?!?! *This copy instruction may need alteration to work correctly, but you get the idea...

'You could just use one flag bit, but a file copy can be interrupted in some computers, so I like to use two separate flags to indicate that, and only set the SORT_DN flag when the mass move instruction is complete.

'If you get to 500 recipes and ten seconds or so is too slow, make several passes over this logic per scan to speed it up.

That's my first shot at it ... Hope it helps ... Paul

EDIT: Add something to deal with when the 500th entry is also the last alphabetically. In other words, If N=500 then MOV NewRecipe Recipe(N):OTU NEW_RECIPE...

HOLY KRUD, 5000 RECIPES? I read 500 the first time...Sorry about that...

At 5000 recipes, executing 1 iteration per 10 mSec, it takes 5 seconds to shift through all 5000 once (not that once will complete the sorting from scratch, but if it's the last one put in, with a name of AAAAAA, it's 5 seconds worst case to shift to the front).