Jump to content

Sort clusters by one element, stable sort? Non-OOP?


MarkCG

Recommended Posts

Hi all,

In implementing code for machine control from a set of requirements, I found where a the right data structure could make what I thought would be a somewhat complicated task very simple:

A data structure that keeps elements (clusters) sorted by one key element (which will be the priority for me), while at the same time keeping elements with equal key values in the same order that they are inserted (that is to say, the sort algorithm is stable). And allows efficient element insertion / deletion.

The structure could allow only unique elements or not, in the latter case I could manage it so that only unique elements are inserted.

You can use the "sort 1D array" function of an array of clusters, but it will sort taking EVERY element of the cluster into account. Thus elements get moved that I don't want to get moved.

Now Tomi Maila put out this community nuggett back in 2007, where he used variants to implement ordered sets: give it an array of clusters, it sorts them according to value starting with cluster element 0 and keeps only unique elements.

http://ni.lithium.co...ant/td-p/489967

This would be perfect! Fast, unique elements, ordered. But again, It sorts based on ALL elements in the cluster, again moving elements that I do not want to be moved relative to each other.

I need it to sort only on one key value, the priority.

I though priority queue, but how can I easily delete elements by name? I imagine it would involve a lot of queue previewing, dequeueing, and requeuing...

Now before anyone starts telling me off about needing to start using LVOOP (which I want to), I have a good reason!! The code will have to be able to run on LVRT 8.6 , which does not support LVOOP. The program will have to run in test facilities on the other side of the globe, and I have no control over whether or not they will or can upgrade. So it pays to be conservative.

Anyone have any ideas about what I ought to do? I can always write my own, I suppose.

Edited by Sergeant Manners
Link to comment

I would use this approach. It is fast and reliable.

Also, stable, which is pretty important for some sorting applications and particularly OP.

How about making your second element of the cluster be an index that increments by one for each cluster added. Then your sort will never change the order except as required by the first cluster element; all other elements will be ignored..

You've missed guentermueller's link. ;)

Link to comment

You've missed guentermueller's link. ;)

Only skimmed it, but I didn’t think the connection between that link, and the problem of ignoring elements other than the first, is all that obvious (though it can be extrapolated). After all, it’s called “Sort 1D array of clusters by the second element”, the opposite of what the OP wants. Nor is it obvious how to adapt it to using a Variant to hold the set. But add a “creation index” as second element and one can use variant attributes as shown in the Maila nugget, which are faster than linear sorting.

Link to comment

Ah yes, I think the method guentermueller linked to will work just fine, you can sort by any element you want ... first, second, Nth, ignoring other elements. Basically it's method drdjpowell suggested, and altenback used in that post:

How about making your second element of the cluster be an index that increments by one for each cluster added. Then your sort will never change the order except as required by the first cluster element; all other elements will be ignored..

It will also keep elements of the same key value in order of insertion. Perfect... thank you everybody for the suggestions!

Link to comment

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use.