Liberty Unleashed

Scripting => Script Snippets => Topic started by: Windlord on May 02, 2011, 08:30:11 pm

Title: inplace quicksort
Post by: Windlord on May 02, 2011, 08:30:11 pm

Code: (squirrel) [Select]

// Used for inplace quicksort
function swap_arr_elem ( arr, idx1, idx2 )
{
local val1 = arr[ idx1 ], val2 = arr[ idx2 ];
arr[ idx1 ] = val2;
arr[ idx2 ] = val1;
return arr;
}

// Quicksort function for Squirrel
function sort ( arr, left = 0, right = 0 )
{
if ( !right ) right = arr.len() - 1;
local diff = right - left;
if ( diff < 1 ) return arr;
if ( diff == 1 && arr[ left ] <= arr[ right ] ) return arr;

local pivot = floor( arr.len() / 2 ), pidx = left;
arr = swap_arr_elem( arr, pivot, right );
pivot = arr[ right ];
for ( local i = left; i < right; i++ )
{
if ( arr[ i ] <= pivot )
{
arr = swap_arr_elem( arr, i, pidx );
pidx++;
}
}
arr = swap_arr_elem( arr, right, pidx );
arr = sort( arr, left, pidx - 1 );
arr = sort( arr, pidx + 1, right );
return arr;
}
If you use sort( array ), the array will be sorted in ascending order.

Edit: Turns out Squirrel has Array.sort() (ref. http://squirrel-lang.org/doc/squirrel3.html#d0e2350)