Sort 1D array of clusters by the second element in the cluster

[Darren]

I was all ready to admit defeat, but I decided to benchmark.  Turns out with a 500,000 element cluster array, my version is actually about 10% faster!  But I will admit that mine probably allocates more memory.

-D

[Kevin_Price]

I always assumed that sorting such a cluster will always put sort according to the ENTIRE data set.  It just so happens that the first element is most significant.  Given two clusters with the same first element, the relative "size" of the second element will then determine the order, no?

Yeah, that's right.  If the first element is a "tie", the second element is the tie-breaker.  And if the second is also a tie, the third is the tie-breaker, etc.  I'm not sure I've tested beyond that point, but I would assume the "etc." is valid.

I've always thought of the sort routine treating the entire cluster as a single (flattened) value.

Hmmmm.  I never thought of that.  Do you mean like a "flattened to string"?  I kinda doubt that, because you'd get different sort behavior for multi-byte integers depending on endian-ness.  I would hope that the comparisons are actually type-dependent.

-Kevin P.

[Darren]

Yes, Kevin, your "etc." assumption is valid...the cluster sort will keep traveling down the order of the elements, all the way to the end if necessary, until it finds a "tie breaker".

-D

[pincpanter]

This also means that, although very elegant (I really like it), Altenbach's solution might give different results than Darren's one.

Paolo

[Kevin_Price]

Right.  Altenbach's solution would use the index in the array as a tie-breaker.  Since this is guaranteed unique, no further tie-breaking is needed. Darren's would use the 1st cluster element, then 3rd, 4th, etc.  Altenbach's will not re-order array elements with identical 2nd cluster elements.  Darren's could.

These are further considerations for the "best" solution.  Minor variations of these examples may be even better yet -- it'll depend on your app. 

-Kevin P.

[altenbach]

---

@Darren wrote:

I was all ready to admit defeat, but I decided to benchmark.  Turns out with a 500,000 element cluster array, my version is actually about 10% faster!  But I will admit that mine probably allocates more memory.

---

If I remember right, both are relatively similar to some of the openG sorting variants (I don't have them currently installed, so I cannot check). Yes, in this particular case, the times should be quite similar. I believe the tide would turn in my favor of you would try to sort an array where the cluster is very complex (many cluster elements, containing arrays and other clusters, etc). I do the sorting on a very small cluster, while you would do the sorting on the entire freight train. 😉

If you still have your benchmark code, try to add a third element to the cluster and see if the times get more similar. 

And yes, as others have mentioned, the results will be probably be different in case of duplicate elements.

[Darren]

I would say that the sort ordering of my solution is preferable, since it mimics the inherent sort ordering of the Sort 1D Array function on clusters.  Except in my case, instead of sorting based on 1st, 2nd, 3rd, 4th, etc. elements, I sort on 2nd, 1st, 3rd, 4th...in other words, I do the exact same kind of cluster sort, but you can specify which element is the first considered.

-D

[Kevin_Price]

Re: "preferable" sort order.  I see Darren's point that in most ways, his method retains the normal use of 1D sort on a cluster.  The sort-of exception is this: whatever situation may make a person prefer to sort based on the 2nd element rather than the default 1st may also mean that they don't want the 1st element to matter at all in the sort. 

Clearly either method can be amended by inserting more than one element from the original cluster into the sort cluster using any desirable tie-breaking order.  With D's method, you can't entirely ignore the precedence of the 1st element while in A's method you can't entirely ignore the order of the original array.

Did anyone do more benchmarking with large arrays of complex clusters?  I'm really curious now.  While I like the elegant look of D's approach, I've learned it's rarely wise to bet against altenbach when it comes to code efficiency.

-Kevin P.

[Hansa]

Hello Folks,

I am just a beginner with LabView and start enjoying the labview coding more due to these discussion forums. I would like to thank everyone and specially Darren & Altenbach for their contribution to the solution of my coding problem -- "Sorting 1D array with second cluster element" (so called a small problem earlier ........ its complex as one dig in more). All these discussions are very helpful and a good learning experience for me.

Just as a curiosity, how you will benchmark any .vi in terms of speed amd memory utilization? Thanks.

Manu

[Darren]

Check out the LabVIEW Help on the VI Profiler tool...it can help you learn about execution time and memory usage of your VIs.

Or you can use the ultra-easy method of dropping a flat sequence structure around your code, creating a frame before and after, sticking a Tick Count function in both, and subtracting the tick count from the first frame from the tick count in the second frame...voila...the execution time of your code in milliseconds!

-D