assert_sort — A flexible sorting function.
y = assert_sort ( x ) y = assert_sort ( x , direction ) y = assert_sort ( x , direction , compfun ) y = assert_sort ( x , direction , compfun , callback ) [ y , indices ] = assert_sort ( ... )
a matrix of doubles or a list, the values to sort.
a 1x1 matrix of booleans, the direction of sort. If direction=%t, increasing sorting is used. If direction=%f, decreasing sorting is used. (Default direction=%t, i.e., increasing). If direction=[], then default direction=%t is used.
a function or a list, the comparison function. If not provided, or if compfun=[], then the default value compfun=assert_compare is used.
a function, an output function. If not provided, or if callback=[], then the default value callback=[] is used, meaning that no function is called back.
a matrix of doubles or a list, the sorted values
a matrix of floating point integers, the permutation necessary to get the sorted values. We always have and(x(indices)==y).
Sort a matrix or a list in increasing order.
If x is a list, the user must provide a comparison function, as no default comparison function is available for this data type.
If no comparison function is given, uses the default operator "<". If compfun is a function, it must have the header :
order = compfun ( x , y )
where order=-1 if x < y, order=0 if x==y, order +1 if x > y.
If compfun is a list, its first element is expected to be a function and the remaining elements are expected to be the additionnal input arguments of the comparison function. For example, if compfun=list(myfun,a1,a2,...,an), the comparison function myfun must have the header:
order = myfun ( x , y , a1, a2, ..., an )
If callback is a function, it must have the header :
callback ( status , x , imin , imax )
where status is a string, x is the current data, imin and imax are floating point integers. The values of status are status="start","in","out","stop". The "start" status appears only once, at the very begining. The "stop" status appears only once, at the very end. The "in" status appears when we enter in the recursive function. The "out" status appears when we leave the recursive function. The imin and imax variables contain the global indices which are currently modified in the recursive call. These indices correspond to the values which are to be modified in the level 0 array to be sorted, as opposed to the array currently being processed at the current level. These indices are necessary, since the function basically know only the current values to be processed, which do not reflect their original positions.
The algorithm is a merge-sort, based on a recursive call of the function, with increasingly small data.
This implementation avoids the overhead caused by arguments checking. For that purpose, the argument checking is done at the main level and this is done once for all. Then it uses an internal recursive function without any checking.
TODO : add a "unique" option, which discards equal elements.
// Sort x in increasing order x = [4 5 1 2 3] y = assert_sort ( x ) // Get the indices x = [4 5 1 2 3] [y,indices] = assert_sort ( x ) x(indices)==y // Sort x in decreasing order x = [4 5 1 2 3]; y = assert_sort ( x , %f ) // Use a customized comparison function: // sort into decreasing order. function order = myorder ( x , y ) if ( x < y ) then order = 1 elseif ( x==y ) then order = 0 else order = -1 end endfunction x = [4 5 1 2 3] // Notice that we use the default direction (i.e. increasing) // by setting direction to the empty matrix []. y = assert_sort ( x , [] , myorder ) // Use a customized comparison function: // sort real values into increasing order, // with an absolute tolerance. function order = myrealorder ( x , y , atol ) if ( abs(x-y)<atol ) then order = 0 elseif ( x < y ) then order = -1 else order = 1 end endfunction x = [1,2,1.2347,1.2346,1.2345,3,4] atol = 1.e-3 compfun = list(myrealorder,atol) y = assert_sort ( x , [] , compfun ) // Notice that the basic comparison function would // produce a difference sorted matrix. assert_sort ( x ) // See that this is a stable sort. // Notice that the equal values are not moved. y = assert_sort ( x , %f , compfun ) // Check that we can sort lists. // We consider list of elements, where each element // is a couple. The order depends on the first element (denoted "x"), // then the second element (denoted "y"), in case of tie. z = list(); z(1) = list(6,5); z(2) = list(5,4); z(3) = list(4,3); z(4) = list(3,2); z(5) = list(2,1); z(6) = list(1,0); sci2exp(zsorted) // Use a customized comparison function: // sort into increasing order. function order = myorder2 ( a , b ) ax = a(1) ay = a(2) bx = b(1) by = b(2) if ( ax == bx ) then if ( ay == by ) then order = 0 elseif ( ay < by ) then order = -1 else order = 1 end elseif ( ax < bx ) then order = -1 else order = 1 end endfunction zsorted = assert_sort(z,[],myorder2); sci2exp(zsorted) // Use a callback to print the status of sorting function mycb ( status , x , imin , imax ) mprintf("%s: (%d,%d) : %s\n",status,imin,imax,sci2exp(x)) endfunction // Sort this into [1 2 3 4 5] x = [4 5 1 2 3]; // Notice that we set compfun = [], so that the default // comparison function is used. y = assert_sort ( x , [] , [] , mycb ); // Display a graphical demo of the sorting process function mycb2 ( status , x , imin , imax ) n = length(x) if ( status == "start") then h = scf() xp = 1:n yp = x plot(xp,yp,"b*") titlestr = "Merge sort n="+string(n)+" indices = ("+string(imin)+","+string(imax)+")" xtitle(titlestr,"Rank","Value") elseif ( status == "out") then h = gcf() h.children.children.children.data(imin:imax,2) = x titlestr = "Merge sort n="+string(n)+" indices = ("+string(imin)+","+string(imax)+")" h.children.title.text = titlestr end endfunction N = 50; // Take the values 1,2,...,50 and permute them randomly x = (1:50)'; x = grand(1,"prm",x); y = assert_sort ( x , [] , [] , mycb2 );