Prev: identification toolbox transfer function
Next: Adaptive Neural Network
From: Bruno Luong on 10 Jul 2010 06:21
The SORTROWS command seems to accept SPARSE matrix, but it is very slow possibly because of slow ROW accessing I mentioned earlier.

In any case, I dig out one of my implementation of HEAPSORT below. With this code you could have few more possibilities to play around with (reverse column/row, inplace mex implementation of comparison operator, etc...).

% Bruno

function a = heapsort(a, ltfun, varargin)
% function a = heapsort(a, ltfun, param1, ...)
%
% Sort the vector A with custumized comparison function.
% ltfun(ai, aj, param1, ...) must return TRUE when ai < aj,
% where ai, aj are two elements of a(:), "<" is user-specific relation
%
% Method: Heapsort algorithm.
%
% Example:
% % Data
% a = ceil(10*rand(5,7))
% % Function to compare two rows of matrix a
% ltfun = @(i,j,a) issorted(a([i j],:),'rows');
%
% idx = heapsort(1:size(a,1),ltfun,a);
%
% asorted = a(idx,:)
% issorted(asorted, 'rows')
%
% Author: Bruno Luong <brunoluong@????.com>

% Defauut comparison function
if nargin<2 || isempty(ltfun)
ltfun = @lt;
end

k = length(a);

%%
% sucessively insert elements to the heap
for last=1:k
child = last;
parent = floor(child/2);
ai = a(last);
% up-heap loop of ai
while parent>0
% heap condition violated
if ltfun(a(parent), ai, varargin{:}) % a(parent) < ai % comparison
a(child) = a(parent);
child = parent;
parent = floor(child/2);
else
break % of while-loop, heap ok
end
end % while loop

a(child) = ai; % here is the final home of ai
end % for-loop

%%
% Remove heap root (currently largest), replace it by the last element
% then make modified heap valid again
for last=k:-1:1
ai = a(last); % try to move ai at the root then move it down
a(last) = a(1); % push the max (root of the heap) to the position
parent = 1;
% down-heap loop of ai
while true
c1 = 2*parent;
if c1 >= last % no child
break
end
left = a(c1);
if c1 == last-1 % there is no right leaf
child = c1;
ac = left;
else
c2 = c1+1;
right = a(c2);
if ltfun(left,right,varargin{:}) % left < right % which leaf is the largest
child = c2;
ac = right;
else
child = c1;
ac = left;
end
end % if

% heap condition violated
if ltfun(ai,ac,varargin{:}) % ai < ac % comparison
a(parent) = ac;
parent = child;
else
break % of while-loop, heap ok
end

end % while loop

a(parent) = ai; % here is the final home of ai
end % for-loop

end % heapsort
 | 
Pages: 1
Prev: identification toolbox transfer function
Next: Adaptive Neural Network