OFPEC Forum

Editors Depot - Mission Editing and Scripting => ArmA - Editing/Scripting Resources Beta Testing & Submission => Topic started by: Worldeater on 20 Jan 2009, 20:51:05

Title: Sorting numeric arrays
Post by: Worldeater 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


Title: Re: Sorting numeric arrays
Post by: Mandoble 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.

Title: Re: Sorting numeric arrays
Post by: Worldeater on 21 Jan 2009, 01:41:01

Thanks! :)

About the suggestions:
- done.
- done.

Here it is. (http://www.ofpec.com/forum/index.php?topic=32832.0)

Title: Re: Sorting numeric arrays
Post by: Mandoble on 21 Jan 2009, 08:39:51

Outstanding  :good:

Title: Re: Sorting numeric arrays
Post by: Wolfrug 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 (http://www.ofpec.com/forum/index.php?topic=32832.0) for discussion/downloads. Locking this one.

Wolfrug out.