I need sorting VI that returns the sorted array element's positions in the unsorted array

[RichardBallantyne]

I need a VI that will very quickly (n log n) sort a 1D array of doubles.  This VI should not only output the sorted array, but for each of the sorted array elements, it should also output that sorted array element's position in the unsorted array.  So for example if the input array were:

unsorted_array

4.1

2.3

7.0

5.6

10.2

Then the output arrays would be:

sorted_array

2.3

4.1

5.6

7.0

10.2

indices_array

1 (the value 2.3 is located at position 1 in the unsorted_array)

0 (the value 4.1 is located at position 0 in the unsorted_array)

3 (the value 5.6 is located at position 3 in the unsorted_array)

2 (the value 7.0 is located at position 2 in the unsorted_array)

4 (the value 10.2 is located at position 4 in the unsorted_array)

This way I could generate the sorted_array using just the indices_array and the unsorted_array.  Has anyone written a nifty piece of code to do this?  I did some research on (n log n) sorting algorithms but most of them use recursion which I don't know how to do in LabVIEW.  It would also be nice to have an algorithm like this that could sort an array of strings.

cheers,

Richard

[altenbach]

Try something like the attached example (LabVIEW 7.0). I think it does what you need.

(To understand the code, it is important to know that arrays of clusters are sorted by the first element in the cluster).

Sort array itself sorts also array of strings, so you could just substitute, keeping the rest of the code the same.

Sort array uses a variation of quicksort, so it should have about NlogN complexity.

(If you think you only need the array of indices to later generate the sorted array, it does not make much sense to even do it. To get the indices, you need to sort the array anyway. 😉 You should just sort the plain array directly. 😉

Message Edited by altenbach on 07-13-2005 03:47 PM

[RichardBallantyne]

That code you attached works great!  Thanks!

[E.R]

Try This

[altenbach]

---

@E.R wrote:
Try This

---

Your code is much less efficient than what I posted, and it is not O(NlogN), but O(N²) (a 10x increase in size will  take 100x more time!). It will scale very poorly with large array inputs:

Some casual benchmarks in milliseconds for inputs with random numbers:

N                   My version       Your version         comment

---

1000                      0 ms            100 ms
10000                    20 ms        10054 ms            (already 500 times slower!)
100000                 261 ms          (~17 min)           estimated
1000000              2654 ms       (~28 hours)           estimated

For large arrays, your version cannot be used at all. 😞

[falkpl]

Yes stick with a O(NLogN), there are a few different sorting algorithms with a big O to match this.  Usually when picking a sort or search algorithm you have a trade off between speed and memory use,  since memory is so cheap (my first computer had 2k of RAM) I would optimize for speed.  What algorithm does the array sort function provided by NI use? Anyone know?

[altenbach]

---

@falkpl wrote:

Yes stick with a O(NLogN), there are a few different sorting algorithms with a big O to match this.  Usually when picking a sort or search algorithm you have a trade off between speed and memory use,  since memory is so cheap (my first computer had 2k of RAM) I would optimize for speed.  What algorithm does the array sort function provided by NI use? Anyone know?

---

Quicksort can be implemented fully "in place" in LabVIEW, so it is very efficient in memory use (besides being a very efficient sorting algorithm in general). Optimizations are in predictive pivot selection and in ways to deal with pathological data. A related algorithm is quickselect, used to find the median of an array. Have a look at the Median Coding Challenge

from a while ago for some examples. We had extensive discussion on sorting algorithms here, but I don't think the thread made it to the new forum format. 😞

[falkpl]

Christian,

Thanks for the link, I am too used to the rapid application development and get lazy accepting any pre-canned functions and don't implement my own algorithms much anymore.  Have you seen any algorithms which take advantage of the multi-threading(hyperthreaded) and multiprocessors (parallel algorithms) systems which are so commonplace today.  Congratulations on reaching the 2000 posts mark.

Paul

[shoneill]

HI Falkpl,

I'm not sure about being able to harness a multithreaded approach for a sort algorithm.  I noticed during my Median VI attempt that as soon as the amount of data being processes in parallel was larger than the processor Cache (256k on that machine), the performance dropped like a stone.  Since inter-thread communication (I believe the P4 requires something like 30 clock cycles just to switch "cores" in a hyperthreaded environment)  is definitely much slower than cache operations, multi-threaded code is better suited to algorithms which have multiple un-related data sets.  The constant data swapping between processors or cores will (in my opinion) actually slow down the process.

On the other hand, if you have data sets of around 1GB, then parallel processing may begin to make sense......

Shane.

[altenbach]

In quickselect, only one range is retained after pivoting, while in quicksort, both sides of the pivot point need to processed further. I could imagine a quicksort algorithm where two (or more) seperate code threads nibble at the stack of ranges in parallel. I don't know how well that would work.