image thumbnail

Knuth Heapsort

version 1.0.0.0 (2.1 KB) by Ben Barrowes
Matlab implementation of Knuth's heapsort.

1.8K Downloads

Updated 22 Aug 2007

View License

Use this Matlab heapsort when you want to compare results from heapsorts in other languages/platforms (fortran, C, SciPy, etc.). Matlab's sort preserves the order of matching entries in a list and is thus a "stable" sort. Heapsort is "unstable" in that it does not preserve the order for matching entries (see example below), thus giving different results from Matlab's sort.

This can be useful, for example, when comparing results during a porting of legacy code into matlab.

% [r,TAGS]=tagged_real_heapsort(r,TAGS);
%
% WRITTEN BY BILL LEDSHAM 4/3/80
%
% HEAPSORT FROM ALGORITHM H IN KNUTH VOL. 3 PP 146-147
%
% VARIABLE USAGE:
% r -> INPUT/OUTPUT OF KEYS TO BE SORTED.
% TAGS -> INPUT OUTPUT OF TAGS THAT WILL FOLLOW r IN SORT ORDER
% n -> NUMBER OF KEYS
%
%
% EXAMPLE:
% r=[4,5,1,5,8,5,9,5];
% t=1:8;
% [r,t]=tagged_real_heapsort(r,t)
% r =
% 1 4 5 5 5 5 8 9
% t =
% 3 1 6 2 4 8 5 7
%
% Converted into Matlab by Ben Barrowes 8/07 in part using f2matlab
% (origninal fortran at end of file)

Cite As

Ben Barrowes (2021). Knuth Heapsort (https://www.mathworks.com/matlabcentral/fileexchange/16044-knuth-heapsort), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2007a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!