index = UFget ;
[ignore probs] = sort (index.nnz) ;
nmat = length (probs)
rand ('state', 0) ;

for kprob = 1:nmat

    % get a test problem
    prob = UFget (probs (kprob))
    A = sprand (prob.A) ;   % randomize the values, just to test
    [I J X] = find (A) ;
    nz = length (X) ;
    [m n] = size (A) ;

    % randomly jumble the triplets, just to test
    junk = randperm (nz) ;
    I = I (junk) ;
    J = J (junk) ;
    X = X (junk) ;

    subplot (1,2,1) ; plot (J) ;

    %----------------------------------------------------------------------------
    % now sort in place.  Pretend we don't know A.  Pretend we know
    % the # of rows and columns, however, just so that a matrix with 
    % empty rows/cols won't result in a matrix with smaller dimension.
    %% m = max (I) ;	% this could also be done
    %% n = max (J) ;
    c = zeros (1,n) ;
    for k = 1:nz
	j = J (k) ;
	c (j) = c (j) + 1 ;
    end
    Ap = cumsum ([1 c]) ;
    w = Ap ;
    for col = 1:n
	for k = (Ap (col)) : (Ap (col+1)-1)

	    while (col ~= J(k))
		% the kth triplet is out of place
		ik = I (k) ;
		jk = J (k) ;
		xk = X (k) ;
		% find out where it should go in the final result
		p = w (jk) ;
		w (jk) = w (jk) + 1 ;
		% swap
		I (k) = I (p) ;
		J (k) = J (p) ;
		X (k) = X (p) ;
		I (p) = ik ;
		J (p) = jk ;
		X (p) = xk ;
		% now the kth triplet might still be out of place, but the
		% pth triplet is in its final position.  The pth triplet will
		% not be considered again as a "p"th triplet, since it is
		% inside the sorted range for its column.  Thus, we must
		% eventually place the kth triplet in its final place.
		% The algorithm will progress to the final solution: QED.

		% this is fun ... watch it work
		subplot (1,2,2) ;
		plot (1:nz, J, '-', [k k], [1 n], 'r-') ;
		drawnow

	    end

	    % this is fun ... watch it work
	    subplot (1,2,2) ;
	    plot (1:nz, J, '-', [k k], [1 n], 'r-') ;
	    drawnow

	end
    end
    % now the triplets are sorted again, by increasing column index.
    % The vectors (Ap, I, X) represent a matrix in compressed column form.
    %----------------------------------------------------------------------------

    % check the result.
    subplot (1,2,2) ; plot (J) ;
    [ignore junk] = sort (J) ;
    if (any (junk ~= (1:nz)')) 
	error ('column indices are not sorted') ;
    end
    A2 = sparse (I,J,X, m,n) ;
    err = norm (A-A2,1)
    drawnow
    
    if (err ~= 0)
	pause
    end
end


!DSPAM:44f966ae426423720071!