Array sorting

calo_mir · July 30, 2009

Is there a working, available array sort function?

I know of BIS_fnc_sortNum but unfortunately it just spews errors whatever I give it as parameters, so I assume it's broken (I don't have the errors to hand, right now).

rübe · May 15, 2006

sure. I can offer you the following two search methods:

fn_insertSort.sqf:

/*
  Author:
   rÃ¼be

  Description:
   generic implementation of the insertion sorting algorithm (that's one 
   of the simplest there is). The original list does NOT get altered.

   This sorting algorithm is very sensitive to the initial ordering of 
   the given list and thus only efficient for small/mostly-sorted 
   lists (we swap only adjacent elements!). Use another one for 
   large/totally unsorted lists. (e.g. RUBE_shellSort)

   >> Sedgewick says: "In short, insertion sort is the method of choice
      for `almost sorted` files with few inversions: for such files, it
      will outperform even the sophisticated methods [...]" 

      (e.g. if you have an already sorted list and you wanna add some 
      more to it...)

    - best case: O(n)
    - worst case: O(n^2)

  Parameter(s):
   _this select 0: the list to be sorted (array of any)
   _this select 1: sort value selector/calculator (string or code; optional)
                   - gets passed a list item, must return scalar
                   - if a string gets passed, we compile it first

                   -> if the list does not consist of numbers but a complex 
                      data structure (like arrays), you may pass a simple
                      function, that accesses (or calculates) the "value" 
                      in this structure the list will be sorted on.

                   -> to simply invert the sort order, pass {_this * -1} as
                      second parameter (for numbers).

                      default sorting order is ASCENDING

  Example(s):

   // 1) sorting numbers

   _numbers = [8, 12, 1, 7, 8, 5];
   _sortedNumbers = [_numbers] call RUBE_insertSort

   // result: [1, 5, 7, 8, 8, 12]


   // 2) sorting data structures, calculating comp.-value
   //    and save the result in the given data structure too!

   _players = [
      // player, points, kills, killed
      [player1, 650, 5, 12],
      [player2, 40, 45, 27],
      [player3, 500, 19, 2],
      [player4, 370, 9, 1]
   ];
   // sort function
   _calculatePlayerTable = {
      private ["_points", "_kills", "_killed", "_score"];
      _points = _this select 1;
      _kills = _this select 2;
      _killed = _this select 3;

      _score = ((_points + (_kills * 5) - (_killed * 10)) * -1);
      _this set [4, (abs _score)];

      _score
   };
   _sortedPlayers = [_list, _calculatePlayerTable] call RUBE_insertSort;

   // result: [[player3, ..., 575], [player1, ..., 555], [player4, ..., 405], [player2, ..., 5]]


  Returns:
   sorted list
*/

private ["_list", "_selectSortValue", "_item", "_i", "_j"];

_list = +(_this select 0);
_selectSortValue = { _this };

if ((count _this) > 1) then
{
  if ((typeName (_this select 1)) == "CODE") then
  {
     _selectSortValue = _this select 1;
  } else {
     _selectSortValue = compile (_this select 1);
  };
};

// insert sort
for "_i" from 1 to ((count _list) - 1) do
{
  _item = +(_list select _i);
  _j = 0;
  for [{_j = _i}, {_j > 0}, {_j = _j - 1}] do
  {
     if (((_list select (_j - 1)) call _selectSortValue) < (_item call _selectSortValue)) exitWith {};
     _list set [_j, (_list select (_j - 1))];
  };
  _list set [_j, _item];
};

_list

fn_shellSort.sqf:

/*
  Author:
   rÃ¼be

  Description:
   generic shell sort implementation. The original list does 
   NOT get altered.

   Shellsort is not sensitive to the initial ordering of the
   given list. Hard to compare to other sorting methods but
   shellsort is often the method of choice for many sorting
   applications:

    - acceptable runtime even for moderately large lists,
      (Sedgewick says up to "five thousand elements")
    - yet very easy algorithm.

  Parameter(s):
   _this select 0: the list to be sorted (array of any)
   _this select 1: sort value selector/calculator (string or code; optional)
                   - gets passed a list item, must return scalar
                   - if a string gets passed, we compile it first

                   -> if the list does not consist of numbers but a complex 
                      data structure (like arrays), you may pass a simple
                      function, that accesses (or calculates) the "value" 
                      in this structure the list will be sorted on.

                   -> to simply invert the sort order, pass {_this * -1} as
                      second parameter (for numbers).

                      default sorting order is ASCENDING

  Returns:
   sorted list
*/

private ["_list", "_selectSortValue", "_n", "_cols", "_j", "_k", "_h", "_t", "_i"];

_list = +(_this select 0);
_selectSortValue = { _this };

if ((count _this) > 1) then
{
  if ((typeName (_this select 1)) == "CODE") then
  {
     _selectSortValue = _this select 1;
  } else {
     _selectSortValue = compile (_this select 1);
  };
};

// shell sort
_n = count _list;
// we take the increment sequence (3 * h + 1), which has been shown
// empirically to do well... 
_cols = [3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1];

for "_k" from 0 to ((count _cols) - 1) do
{
  _h = _cols select _k;
  for [{_i = _h}, {_i < _n}, {_i = _i + 1}] do
  {
     _t = _list select _i;
     _j = _i;

     while {(_j >= _h)} do
     {
        if (!(((_list select (_j - _h)) call _selectSortValue) > 
              (_t call _selectSortValue))) exitWith {};
        _list set [_j, (_list select (_j - _h))];
        _j = _j - _h;
     };


     _list set [_j, _t];
  };
};

_list

If you're unsure which one to use, I suggest you try shellSort which is a good sort algorithm for most of the cases. Thanks to the generic selector, you may sort really anything - not only numbers, from nested arrays to objects sorted by some getVariable value maybe..

Edited December 21, 2011 by ruebe

calo_mir · July 30, 2009

Ah, OK. Thanks!

CarlGustaffa · March 13, 2007

I'm having some issues with fn_shellSort, for quite some time now. So, time to give up and ask the experts. The question:

How do I call fn_shellSort within a loop, using code evaluation to make up the sorting key?

My testing works fine if done outside the loop (for "_i" from... syntax), in the debug dialog, and it works fine if I use the unsorted array within the loop. I've tried various types of waitUntils and long sleeps, as well as local and global variables. For testing purposes, I start it from a radio trigger (if it matters, but I don't think so).

The syntax I'm using:

_d_target_names_sorted = [d_target_names,{loc distance [(_this select 0) select 0, (_this select 0) select 1]}] call fn_shellsort;

where loc is given by:

loc = (if(_i == 0) then {d_base_array select 0} else {(_d_target_names_sorted select _i) select 0});

Basically what I'm trying to achieve is to create a "shortest route" list through the Domination targets. Actually slightly more, but this was supposed to be the first step.

Full code with plenty variations I've tried below.

waitUntil {player == player}; //Not really needed when started from radio trigger, but...
d_result = [];
_d_target_names_sorted = [];
sleep 0.55; //                           {        CODE block to attempt to sort target names based on distance from base          }
_d_target_names_sorted = [d_target_names,{(d_base_array select 0) distance [(_this select 0) select 0, (_this select 0) select 1]}] call fn_shellsort;
waitUntil {count _d_target_names_sorted == count d_target_names};
sleep 1;
hint format ["Target_names_sorted:\n\n%1\n\nStarting loop in five sec!",_d_target_names_sorted]; //Correct output when done outside the loop
sleep 5;
//d_random = floor(random 3);
//d_result set [0, _d_target_names_sorted select d_random];
//_name = "New" + format ["%1",(d_result select (count d_result - 1)) select 1];
//_pos = (d_result select (count d_result - 1)) select 0;
//[_name,_pos,"ICON","COLORRED",[0.5,0.5],format ["%1",count d_result - 1],0,"mil_dot"] call XfCreateMarkerLocal;
for "_i" from 0 to ((count d_target_names) - 1) do { //Parathesis overuse, just eliminating all possibilities
//	loc = (if(_i == 0) then {d_base_array select 0} else {(_d_target_names_sorted select _i) select 0}); //Using unsorted names doesn't make a difference
loc = d_base_array select 0; //This doesn't help either
sleep 0.025;
_d_target_names_sorted = [d_target_names,{loc distance [(_this select 0) select 0, (_this select 0) select 1]}] call fn_shellsort;
//	_d_target_names_sorted = d_target_names; //CHECK THIS VERSION HOW THE SCRIPT BEHAVES WHEN IT WORKS!!!
waitUntil {count _d_target_names_sorted > _i-1}; //Doesn't make a difference, no matter how long you wait.
sleep 0.025;
d_result set [_i, (_d_target_names_sorted select _i)]; //Fills up with <null>
//	d_result set [count d_result, (_d_target_names_sorted select _i)]; //Adds only a single <null>
//	d_result = d_result + [_d_target_names_sorted select _i]; //Also adds only a single <null>
//	d_result set [count d_result, _i]; //Contains only [21]
//	d_result set [_i, _i]; //Crazy; [<null>,<null>...etc...,21]
sleep 0.025;
hint format ["i=%1\n\nloc: %2\n\ncurrent:\n %3", _i, loc, _d_target_names_sorted select _i];
sleep 0.04;
};
player globalChat format ["d_target_names_sorted: %1", _d_target_names_sorted];
player globalChat format ["loc: %1", loc];
player globalChat format ["d_result: %1", d_result];
_test = [d_target_names,{loc distance [(_this select 0) select 0, (_this select 0) select 1]}] call fn_shellsort;
player globalChat format ["%1",_test select 5];

Other needed variables, can be defined in init.sqf:

d_target_names =
[
	[[1779.68,11808.1,0],"Nur",900], // 0
	[[3082.35,9922.74,0],"Nagara",900], // 1
	[[6220.99,11111.8,0],"Rasman",900], // 2
	[[5662.6,8936.69,0],"Bastam",900], // 3
	[[9858.96,11464.5,0],"Zavarak",900], // 4
	[[12334.2,10247.7,0],"Karachinar",900], // 5
	[[10721.5,6347.16,0],"Garmsar",900], // 6
	[[9127.56,6757.6,0],"Garmarud",900], // 7
	[[5937.14,7282.13,0],"Falar",900], // 8
	[[5253.33,6177.37,0],"Feruz-Abad",900], // 9
	[[3655.71,4316.29,0],"Sakhe",900], // 10
	[[1466.8,3594.07,0],"Shukurkalay",900], // 11
	[[546.094,2811.05,0],"Chaman",900], // 12
	[[8894.68,5272.33,0],"Timurkalay",900], // 13
	[[4438.04,686.898,0],"Chak Chak",900], // 14
	[[10142.7,2336.75,0],"Chardarakht",900], // 15
	[[2003.28,352.347,0],"Landay",900], // 16
	[[1987.14,7657.36,0],"Mulladost",900], // 17
	[[11528.4,8351.98,0],"Ravanay",900], // 18
	[[1507.13,5701.05,0],"Khushab",900], // 19
	[[2528.11,5068.08,0],"Jilavur",900] // 20
];
d_base_array = [[8006.81,1864.2,0], 500, 200, -210.238];

The function, just slightly rewritten to match how I like things to look, shouldn't be any different from the original:

fn_shellsort = {
private ["_list", "_selectSortValue", "_n", "_cols", "_j", "_k", "_h", "_t"];
_list = +(_this select 0);
_selectSortValue = {_this};
if ((count _this) > 1) then {
	if ((typeName (_this select 1)) == "CODE") then {
		_selectSortValue = _this select 1;
	} else {
		_selectSortValue = compile (_this select 1);
	};
};
_n = count _list;
_cols = [3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1];
for "_k" from 0 to ((count _cols) - 1) do {
	_h = _cols select _k;
	for [{_i = _h}, {_i < _n}, {_i = _i + 1}] do {
		_t = _list select _i;
		_j = _i;
		while {(_j >= _h)} do {
			if (!(((_list select (_j - _h)) call _selectSortValue) > (_t call _selectSortValue))) exitWith {};
			_list set [_j, (_list select (_j - _h))];
			_j = _j - _h;
		};
		_list set [_j, _t];
	};
};
_list
};

Any pointers? Any obvious mistakes? Any coding malpractices? Any suggestions how to do this differently, as I'm kinda "locked" in my way of thinking right now?

Right now, beer and Queens "I'm going slightly mad"... :madtongue:

Edited August 13, 2010 by CarlGustaffa
Paste typo

rübe · May 15, 2006

Any pointers? Any obvious mistakes? Any coding malpractices? ...

Yes, and they're actually on my part.

Without looking at your code in detail, try again, but this time private "_i" in shellSort too, which I didn't list in the private array by mistake. Sorry. :o

Report back, so if it still does not work, I'm going to look at what you're actually doing a bit longer. :)

CarlGustaffa · March 13, 2007

Yup, that did the trick. Back to work then I guess - thanks a lot, much appreciated :D The eyes of you guys, yikes. :p

rübe · May 15, 2006

The eyes of you guys, yikes. :p

Eyes? That's soo yesterday.

Try this: http://forums.bistudio.com/showthread.php?t=104790

...and welcome to the future.

:D

CarlGustaffa · March 13, 2007

Lol, ok. Seen it before and forgot about it. Downloading now, thanks. :)

f2k sel · June 2, 2009

I've been trying to get Ruebe's functions to work but all I'm get is "ANY".

I have tried his example and still get the same result.

Can anyone get them to work and explain how you did it.

Cheers.

rübe · May 15, 2006

Can anyone get them to work and explain how you did it.

Show me your (minimal) code and I will tell you what's going wrong.

(Also there was an "error" - not a code error, only in the comments - in the insertSort function conserning the first example, where _numbers wasn't wrapped in an extra array. Maybe that's your problem?)

f2k sel · June 2, 2009

Show me your (minimal) code and I will tell you what's going wrong.
(Also there was an "error" - not a code error, only in the comments - in the insertSort function conserning the first example, where _numbers wasn't wrapped in an extra array. Maybe that's your problem?)

I was just testing so far, I just have this placed in an init

 numbers = [8, 12, 1, 7, 8, 5];
   sortedNumbers = [numbers] call RUBE_insertSort;
hint format ["%1",sortedNumbers];

rübe · May 15, 2006

I was just testing so far, I just have this placed in an init
 numbers = [8, 12, 1, 7, 8, 5];
   sortedNumbers = [numbers] call RUBE_insertSort;
hint format ["%1",sortedNumbers];

And this is not working for you?

Over here it returns: "[1,5,7,8,8,12]" and that should be fine.

If you wanna sort these numbers in descending way, you'd write

  sortedNumbers = [
     numbers, 
     {(_this * -1)}
  ] call RUBE_insertSort;

Or if you wanna sort "objects" by their distance to another one, you could write:

  sortedObjects = [
     someObjects, 
     {(_this distance toThatObject)}
  ] call RUBE_insertSort;

And as a final remark: if you know that the list your working on is already mostly sorted, then insertSort is fine. On the other hand, if you know, that your list is total disorder, then you should be using shellSort.

If in doubt, I'd recommend to use shellSort, which is faster in most cases.

f2k sel · June 2, 2009

I got it now it simply won't work in a units init without a delay.

Cheers ruebe.

Array sorting

Recommended Posts

calo_mir 10

Share this post

Link to post

Share on other sites

rübe 127

Share this post

Link to post

Share on other sites

calo_mir 10

Share this post

Link to post

Share on other sites

CarlGustaffa 4

Share this post

Link to post

Share on other sites

rübe 127

Share this post

Link to post

Share on other sites

CarlGustaffa 4

Share this post

Link to post

Share on other sites

rübe 127

Share this post

Link to post

Share on other sites

CarlGustaffa 4

Share this post

Link to post

Share on other sites

f2k sel 164

Share this post

Link to post

Share on other sites

rübe 127

Share this post

Link to post

Share on other sites

f2k sel 164

Share this post

Link to post

Share on other sites

rübe 127

Share this post

Link to post

Share on other sites

f2k sel 164

Share this post

Link to post

Share on other sites

Please sign in to comment

Browse

Activity