Home   Help Search Login Register  

Author Topic: Sorting numeric arrays  (Read 1850 times)

0 Members and 1 Guest are viewing this topic.

Offline Worldeater

  • Former Staff
  • ****
  • Suum cuique
Sorting numeric arrays
« on: 20 Jan 2009, 20:51:05 »
I've just stumbled upon a SQF implementation of a bubblesort. Since bubblesort is known to perform terribly bad, here is a quicksort (wrapped in a function library template):


Code: (libStd.sqf) [Select]
/* libStd.sqf
 *
 * NOTES:       This file must be initialized from init.sqf like this:
 *
 *                call compile preprocessFileLineNumbers "libStd.sqf";
 *
 *              Feel free to adjust the #defines to make them meet your
 *              naming scheme.
 */


#define FN_QUICKSORT fnQuicksort


FN_QUICKSORT = {

    /* SYNTAX:      [Array, FirstIndex, LastIndex] call FN_QUICKSORT;
     *
     * PARAMETERS:  Array:       Array to be sorted
     *              FirstIndex:  Indicates where to start sorting
     *              LastIndex:   Indicates where to stop sorting
     *
     * EXAMPLE:     [_myArray, 0, (count _myArray) - 1] call fnQuicksort;
     */

    private ["_a", "_l", "_r", "_i", "_j", "_t"];

    _a = _this select 0;
    _l = _this select 1;
    _r = _this select 2;

    if (_r > _l) then {
        _i = _l - 1;
        _j = _r;
        _t = 0;
        while { true } do {
            scopeName "whileTrue";
            while { _i = _i + 1; (_a select _i) < (_a select _r) } do {};
            while { _j = _j - 1; ((_a select _j) > (_a select _r)) && (_j > _i)} do {};
            if (_i >= _j) then { breakOut "whileTrue" };
            _t = _a select _i;
            _a set [_i, _a select _j];
            _a set [_j, _t];
        };
        _t = _a select _i;
        _a set [_i, _a select _r];
        _a set [_r, _t];
        [_a, _l, _i - 1] call FN_QUICKSORT;
        [_a, _i + 1, _r] call FN_QUICKSORT;
    };

}; // FN_QUICKSORT
try { return true; } finally { return false; }

Offline Mandoble

  • Former Staff
  • ****
    • Grunt ONE and MandoMissile suite
Re: Sorting numeric arrays
« Reply #1 on: 20 Jan 2009, 21:08:25 »
We have here a fine piece of code  :clap:  :good:
I would suggest you to:
- Implement a way to define the sorting criteria, for example using an user defined code function that gets two array members to compare and then using any kind of user made comparisons it returns -1, 1 or 0 to indicate if first element is minor, greater or equal to the second element. And based on that the higher level sorting functions proceeds with the ordering.
- Add a quite basic example mission, and move this to a beta testing thread.

Offline Worldeater

  • Former Staff
  • ****
  • Suum cuique
Re: Sorting numeric arrays
« Reply #2 on: 21 Jan 2009, 01:41:01 »
Thanks! :)

About the suggestions:
- done.
- done.

Here it is.
try { return true; } finally { return false; }

Offline Mandoble

  • Former Staff
  • ****
    • Grunt ONE and MandoMissile suite
Re: Sorting numeric arrays
« Reply #3 on: 21 Jan 2009, 08:39:51 »
Outstanding  :good:

Offline Wolfrug

  • Addons Depot
  • Former Staff
  • ****
  • Official OFPEC Old Timer
Re: Sorting numeric arrays
« Reply #4 on: 21 Jan 2009, 09:18:11 »
Oh for pete's sake Mandoble :P You couldn't just have moved this topic instead?  ::)

Go here for discussion/downloads. Locking this one.

Wolfrug out.
"When 900 years YOU reach, look as good you will not!"