Sorting a list of nodes in the tree

If you have ever needed to sort a list of number nodes in your tree, read on...

Perhaps you resorted to using 2 nested for loops. This is probably fine for quite small lists, but as you get up to dozens or hundreds of nodes in your list, that method is quite inefficient. Especially if you're sorting the list during the simulation run.

I've coded up two of the best list sorting algorithms to work in Flexsim's tree. This will be somewhat of an advanced exercise unless you have a good computer science background, or you're fairly experienced in Flexsim's tree structure and flexscript. If this doesn't describe you, but you still need to sort a list, feel free to post any questions below.

If you download this listSorting.zip file and extract it, you'll find two .t files. Each of the .t files is a user command and should be added to your model in this location:

model/Tools/GlobalVarGen>variables/commands

If you don't have those nodes in your tree, first try opening the User Command interface (Main menu > Tools > User Commands) and adding a new user command. Then close the User Commands window and dive into the tree again.

After adding these .t files to nodes in your tree, you may need to reopen the User Commands GUI, and perhaps close it again, in order to register the new commands. Now you should be able to use these new commands.

Quicksort and mergesort are among the fastest algorithms for sorting a list. See http://en.wikipedia.org/wiki/Quicksort and http://en.wikipedia.org/wiki/Merge_sort to learn more.

Both of these user commands take the same set of parameters and will end up with the same result - a sorted list of numeric nodes. However, the guts of each command are quite different. One command may be much more efficient (execute faster) for your list of data than the other. If you're just doing a one-time sort, then it probably doesn't matter which command you use. However, if for some reason you're running the command while your simulation is running, you'll want to experiment with both commands to see which gives you better performance. It will largely depend on the size and randomness of your list of nodes.

With just a few modifications these commands could be used to sort a table, in place of Flexsim's sorttable() command. This might be your solution if you've wanted to use sorttable() to sort in descending order, which these user commands can handle.

As a quick reference, you can use these commands as follows:

treenode mylist = rank(mydata, i);
quicksort(mylist);

This will use default values to sort mylist in ascending order. Or you can enter in some optional parameters to change the sorting order or sort just a portion of the list. Check out the user command descriptions from the User Command interface for more info.

Hopefully these will be helpful to someone.

Ben

It seems the above quicksort does not work in some cases. mergsort is fine.

Use quicksort(so(), 1, 1, 10) on the following list:
10
2
3
4
5
6
7
8
9
1

It will return:
1
3
2
4
5
6
7
8
9
10

It's a small error in the loops of quicksort:

Add the "=" in row 29 and 49:

for(int i=minrank; i<=maxrank; i++){

Here is an interesting technique I have used for the past years:

https://sites.google.com/site/comput...rt---version-3

For small vectors (less than 25 entries), it is faster than bubble sort. For large vectors (more than 10,000 entries), I cannot differentiate between quick sort and o-sort in terms of speed. What was reported by the author is kind of a worst case scenario.

From my opinion, this algorithm is very attractive because of its simplicity, stability, speed, exactness and by the fact it is efficient for small and large vectors.