File Exchange

image thumbnail

Knuth Heapsort

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

0 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)

Comments and Ratings (1)

John D'Errico

This may be a silly question on my part. But why would anyone want a slow sorting routine, based on a direct conversion from fortran to matlab, when we already have a much faster sort facility built into matlab?

If the only purpose of the code is for some students to cheat on their CS homework by handing this in, the programming style clearly suggests a f2matlab conversion of 30 year old fortan. The lack of internal comments makes it hardly useful anyway to a student.

By the way, as a matter of programming style, it seems silly to have to pass in the vector of tags==1:n. While this was appropriate in fortran, its just silly in matlab.

Lets look at a quick timing test:

>> n = 10000;X = rand(1,n);tags = 1:n;
>> tic,tagged_real_heapsort(X,tags);toc
Elapsed time is 0.514219 seconds.

>> tic,sort(X);toc
Elapsed time is 0.002858 seconds.

I can't even argue that this submission needs improvement, since, well, sort does a FAR better job. Sort also returns tags. This submission serves absolutely no purpose on the file exchange.

Updates

1.0.0.0

Slightly updated file, updated description.

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