Skip to content
This repository
tree: 3d4846b42a
Fetching contributors…

Cannot retrieve contributors at this time

file 125 lines (110 sloc) 3.465 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
namespace Rosella.Query.Sort
{
    /* Sorting Routines
    */

    // lightly-optimized implementation of Quicksort.
    function quicksort(var d, int s, int n, var cmp)
    {
        int last = n-1;
        while (last > s) {
            int pivot = s + int((n - s) / 2);
            int store = s;

            var piv = array_swap(d, pivot, last);

            for(int ix = s; ix < last; ix++) {
                if (cmp(d[ix], piv) < 0) {
                    array_swap(d, store, ix);
                    store++;
                }
            }

            array_swap(d, last, store);
            pivot = store;
            quicksort(d, s, pivot, cmp);
            s = pivot + 1;
        }
    }

    // Transition threshold below which the hybrid sort switches to insertion
    // sort instead of quicksort
    const int HYBRID_SORT_TRANSITION = 6;

    // Quicksort + Insertion Sort hybrid. For arrays shorter than a certain
    // length, switch to insertion sort.
    function hybrid_quicksort(var d, int s, int n, var cmp)
    {
        int last = n-1;
        while (last > s) {
            if ((last - s) < HYBRID_SORT_TRANSITION) {
                for (int x = s + 1; x < n; x++)
                {
                    var val = d[x];
                    int j = x - 1;
                    while (j >= 0 && cmp(val, d[j]) < 0)
                    {
                        d[j + 1] = d[j];
                        j--;
                    }
                    d[j + 1] = val;
                }
                return;
            }
            int pivot = s + int((n - s) / 2);
            int store = s;
            var tmp;

            var piv = d[pivot];
            d[pivot] = d[last];
            d[last] = piv;

            for(int ix = s; ix < last; ix++) {
                if (cmp(d[ix], piv) < 0) {
                    tmp = d[store];
                    d[store] = d[ix];
                    d[ix] = tmp;
                    store++;
                }
            }

            tmp = d[last];
            d[last] = d[store];
            d[store] = tmp;
            pivot = store;
            hybrid_quicksort(d, s, pivot, cmp);
            s = pivot + 1;
        }
    }

    // Timsort the array. Best used when the array is already mostly sorted
    // or reverse-sorted.
    function timsort(var d, var cmp)
    {
        var ts = new Rosella.Query.Sort.Timsort(cmp);
        ts.sort(d, 0, elements(d), cmp);
    }

    /* Default Sort Comparison Routines
    */

    // Default sort routine.
    function get_default_comparer()
    {
        return function (var a, var b) {
            return compare_pmcs(a, b);
        };
    }

    // Reverse sort routine
    function get_reverse_comparer()
    {
        return function (var a, var b) {
            return -(compare_pmcs(a, b));
        };
    }

    // Null sort-routine. Leave the array unsorted (for stable sort algorithms
    // only)
    function get_unmoving_comparer()
    {
        return function (var a, var b) {
            return 0;
        };
    }

    // Randomizing sort routine. "sort" the array into a random order. Not for
    // use with a sort algorithm that is going to verify the array is sorted
    // (because comparisons randomly change and verification will fail).
    function get_randomizing_comparer()
    {
        return function (var a, var b) {
            return Rosella.Random.default_uniform_random().get_integer(0, 2) - 1;
        };
    }
}
Something went wrong with that request. Please try again.