Desert Dog

//-------------------------------------------------
// Author:          GML written by Desert Dog
// Name:            shuffle_array( size );
// Description:     Takes myArray and randomly shuffles
//                  the values around inside it, from index 0 - size  
// Reference        http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* shuffle_array( size ) */

var temp, randomIndex, size;
size = argument0;

for ( i = 1; i < size; i += 1)
{
    randomIndex = irandom_range( 0, i );
    temp = myArray[ i ];
    myArray[ i ] = myArray[ randomIndex ];
    myArray[ randomIndex ] = temp;    
}

//-------------------------------------------------
// Author:          GML written by Desert Dog
// Name:            array_in_order( size );
// Description:     Checks myArray, and sees if from index
//                  0 - size, the array is in order from
//                  least to greatest
// Arguments:       size - size of array to shuffle
// Return:          true or false
//-------------------------------------------------

/* array_in_order( size ) */
var size;
size = argument0;

for ( i = 1; i < size; i += 1 )
{
    if ( myArray[ i ] < myArray[ i - 1 ] )
        return false;
}
return true;

//-------------------------------------------------
// Author:          GML written by Desert Dog
// Name:            simple_bubblesort( size );
// Description:     Takes myArray and sorts it with a simplist,
//                  but not efficient, bubblesort
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* simple_bubblesort( size ) */

var temp, size;
size = argument0;

for ( i = 0; i < size; i += 1 )
{
    for ( j = i + 1; j < size; j += 1 )
    {
        if ( myArray[ j ] < myArray[ i ] )
        {
            temp = myArray[ j ];
            myArray[ j ] = myArray[ i ];
            myArray[ i ] = temp;
        }
    }
}   

//-------------------------------------------------
// Author:          GML written by Desert Dog
// Name:            bubblesort( size );
// Description:     Takes myArray and sorts it using the famous
//                  bubblesort algorithm.
// Reference:       http://en.wikipedia.org/wiki/Bubblesort
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* bubblesort( size ) */

var temp, swapped, n;
n = argument0;

do 
{
    swapped = false;
    for ( i = 1; i < n; i += 1 )
    {
        if ( myArray[ i - 1 ] > myArray[ i ] )
        {
            temp = myArray[ i ];
            myArray[ i ] = myArray[ i - 1 ];
            myArray[ i - 1 ] = temp;
            swapped = true;
        }
    }
    n = n - 1;
} until( not swapped);

//-------------------------------------------------
// Author:          GML written by Desert Dog
// Name:            bogosort( size );
// Description:     Takes myArray and sorts it using the infamous
//                  bogosort algorithm.
// Reference:       http://en.wikipedia.org/wiki/Bogosort
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* bogosort( size ) */

var size;
size = argument0;

while( not array_in_order( size ) )
    shuffle_array( size );

//-------------------------------------------------
// Author:          GML written by Desert Dog
// Name:            insertion_sort( size );
// Description:     Takes myArray and sorts it using insertion sort.
// Reference:       http://en.wikipedia.org/wiki/Insertion_sort
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* insertion_sort( size ) */

var size, item, iHole;
size = argument0;

for ( i = 1; i < size; i += 1 )
{
    item = myArray[ i ];   
    iHole = i;
    
    if ( iHole > 0 )
    {
        while ( myArray[ iHole - 1 ] > item )
        {
            myArray[ iHole ] = myArray[ iHole - 1 ];
            iHole = iHole - 1;
            if ( iHole <= 0 )
                break;
        } 
    }
    myArray[ iHole ] = item;
}

//-------------------------------------------------
// Author:          Desert Dog - GML version
//                  Darel Rex Finley - Original C implementation
// Name:            quick( size );
// Description:     Takes myArray and sorts it using quicksort
// Reference:       http://en.wikipedia.org/wiki/Quicksort
//                  http://alienryderflex.com/quicksort/
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* quicksort( size ) */

var size, piv, beg1, end1, i, L, R, swap;

size = argument0;
if ( size <= 1 )
    exit;
    
i = 0;
beg[ 0 ] = 0;
end1[ 0 ] = size;

while( i >= 0 )
{
    L = beg[ i ];
    R = end1[ i ] - 1;
    
    if ( L < R )
    {
        piv = myArray[ L ];
        while( L < R )
        {
            while( myArray[ R ] >= piv && L < R )
                R -= 1;
            if ( L < R )
            {
                myArray[ L ] = myArray[ R ]
                L += 1;
            }
            
            while( myArray[ L ] <= piv && L < R )
                L += 1;
            if ( L < R )
            {
                myArray[ R ] = myArray[ L ]
                R -= 1;
            }
        }
        
        myArray[ L ] = piv;
        beg[ i + 1 ] = L + 1;
        end1[ i + 1 ] = end1[ i ];
        end1[ i ] = L;
        i += 1;
        
        if ( end1[ i ] - beg[ i ] > end1[ i - 1 ] - beg[ i - 1 ] )
        {
            swap = beg[ i ];
            beg[ i ] = beg[ i - 1 ];
            beg[ i - 1 ] = swap;
            
            swap = end1[ i ];
            end1[ i ] = end1[ i - 1];
            end1[ i - 1 ] = swap;
        }
    }
    else
        i -= 1;
}

//-------------------------------------------------
// Author:          Desert Dog - GML version
// Name:            mergesort( size );
// Description:     Takes myArray and sorts it using quicksort
// Reference:       http://en.wikipedia.org/wiki/Merge_sort
//                  Bottom-up, non-recursive version
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* mergesort( size ) */


var width, size;
size = argument0;

for ( width = 1; width < size; width = 2 * width )
{
    var i;
    for ( i = 0; i < size; i = i + 2 * width )
    {
        //bottom-up merge
        var iLeft, iRight, iEnd, B;
        iLeft = i;
        iRight = min( i + width, size );
        iEnd = min( i + 2 * width, size );
        
        var i0, i1, j;
        i0 = iLeft;
        i1 = iRight;
        
        for ( j = iLeft; j < iEnd; j += 1 )
        {
            if ( i0 < iRight )
            {
                if ( i1 >= iEnd )    
                {
                    B[ j ] = myArray[ i0 ];
                    i0 = i0 + 1;
                }
                else
                    if ( myArray[ i0 ] <= myArray[ i1 ] )
                    {
                        B[ j ] = myArray[ i0 ];
                        i0 = i0 + 1;
                    }
                    else
                    {
                        B[ j ] = myArray[ i1 ];
                        i1 = i1 + 1;
                    }
            }
            else
            {
                B[ j ] = myArray[ i1 ];
                i1 = i1 + 1;
            }
        }
    }
    //copy array B to myArray.
    for ( i = 0; i < size; i += 1 )
    {
        myArray[ i ] = B[ i ];
    }
}

//-------------------------------------------------
// Author:          Desert Dog - GML version
// Name:            heapsort( size );
// Description:     Takes myArray and sorts it using quicksort
// Reference:       http://en.wikipedia.org/wiki/Heapsort
// Arguments:       size - size of array to shuffle
// Return:          None
//-------------------------------------------------

/* heapsort( size ) */


var size, temp;
size = argument0;

//heapify
var start;
start = ( size - 2 ) / 2;

while ( start >= 0 )
{
    //siftdown
    var start2, end2, root;
    start2 = start;
    end2 = size - 1;
    
    root = start2;
    while ( root * 2 + 1 <= end2 )
    {
        var child, swap;
        child = root * 2 + 1;
        swap = root;
        
        if ( myArray[ swap ] < myArray[ child ] )
            swap = child;
            
        if ( child + 1 <= end2 )
            if ( myArray[ swap ] < myArray[ child + 1 ] )
                swap = child + 1;
            
        if ( swap != root )
        {
            temp = myArray[ root ];
            myArray[ root ] = myArray[ swap ];
            myArray[ swap ] = temp;
            
            root = swap;
        }
        else
            break;
    }
    //end siftdown
    start = start - 1;
}
//end heapify

var end1;
end1 = size - 1;

while( end1 > 0 )
{
    temp = myArray[ end1 ];
    myArray[ end1 ] = myArray[ 0 ];
    myArray[ 0 ] = temp;
    
    end1 = end1 - 1;
    
    //siftdown
    var start2, end2, root;
    start2 = 0;
    end2 = end1;
    
    root = start2;
    while ( root * 2 + 1 <= end2 )
    {
        var child, swap;
        child = root * 2 + 1;
        swap = root;
        
        if ( myArray[ swap ] < myArray[ child ] )
            swap = child;
            
        if ( child + 1 <= end2 )
            if ( myArray[ swap ] < myArray[ child + 1 ] )
                swap = child + 1;
            
        if ( swap != root )
        {
            temp = myArray[ root ];
            myArray[ root ] = myArray[ swap ];
            myArray[ swap ] = temp;
            
            root = swap;
        }
        else
            break;
    }
    //end siftdown
}