function [ indx, i, j ] = sort_heap_external ( n, indx, isgn ) %*****************************************************************************80 % %% SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order. % % Discussion: % % The actual list of data is not passed to the routine. Hence this % routine may be used to sort integers, reals, numbers, names, % dates, shoe sizes, and so on. After each call, the routine asks % the user to compare or interchange two items, until a special % return value signals that the sorting is completed. % % Licensing: % % This code is distributed under the GNU LGPL license. % % Modified: % % 12 February 2010 % % Author: % % Original FORTRAN77 version by Albert Nijenhuis, Herbert Wilf. % MATLAB version by John Burkardt % % Reference: % % Albert Nijenhuis, Herbert Wilf. % Combinatorial Algorithms, % Academic Press, 1978, second edition, % ISBN 0-12-519260-6. % % Parameters: % % Input, integer N, the number of items to be sorted. % % Input, integer INDX, the main communication signal. % The user must set INDX to 0 before the first call. % Thereafter, the user should set the input value of INDX % to the output value from the previous call. % % Input, integer ISGN, results of comparison of elements I and J. % (Used only when the previous call returned INDX less than 0). % ISGN <= 0 means I is less than or equal to J; % 0 <= ISGN means I is greater than or equal to J. % % Output, integer INDX, the main communication signal. % If INDX is % % greater than 0, the user should: % * interchange items I and J; % * call again. % % less than 0, the user should: % * compare items I and J; % * set ISGN = -1 if I < J, ISGN = +1 if J < I; % * call again. % % equal to 0, the sorting is done. % % Output, integer I, J, the indices of two items. % On return with INDX positive, elements I and J should be interchanged. % On return with INDX negative, elements I and J should be compared, and % the result reported in ISGN on the next call. % persistent i_save; persistent j_save; persistent k; persistent k1; persistent n1; if ( isempty ( i_save ) ) i_save = -1; end if ( isempty ( j_save ) ) j_save = -1; end % % INDX = 0: This is the first call. % if ( indx == 0 ) k = floor ( n / 2 ); k1 = k; n1 = n; % % INDX < 0: The user is returning the results of a comparison. % elseif ( indx < 0 ) if ( indx == -2 ) if ( isgn < 0 ) i_save = i_save + 1; end j_save = k1; k1 = i_save; indx = -1; i = i_save; j = j_save; return; end if ( 0 < isgn ) indx = 2; i = i_save; j = j_save; return; end if ( k <= 1 ) if ( n1 == 1 ) i_save = 0; j_save = 0; indx = 0; else i_save = n1; n1 = n1 - 1; j_save = 1; indx = 1; end i = i_save; j = j_save; return; end k = k - 1; k1 = k; % % 0 < INDX, the user was asked to make an interchange. % elseif ( indx == 1 ) k1 = k; end while ( 1 ) i_save = 2 * k1; if ( i_save == n1 ) j_save = k1; k1 = i_save; indx = -1; i = i_save; j = j_save; return; elseif ( i_save <= n1 ) j_save = i_save + 1; indx = -2; i = i_save; j = j_save; return; end if ( k <= 1 ) break; end k = k - 1; k1 = k; end if ( n1 == 1 ) i_save = 0; j_save = 0; indx = 0; i = i_save; j = j_save; else i_save = n1; n1 = n1 - 1; j_save = 1; indx = 1; i = i_save; j = j_save; end return end