6 ms·
Of course this is a n^2 sort. Combinatorial Algorithms by Nijenhuis and Wilf, 1975, has a 23 lines Fortran implementation of Heapsort, a n log n sort. It is ava
by mjcohen 6y ago
Of course this is a n^2 sort. Combinatorial Algorithms by Nijenhuis and Wilf, 1975, has a 23 lines Fortran implementation of Heapsort, a n log n sort. It is available on the web and easily found, so I am going to list it here. I am not going to attempt to convert it to C.
Note: Enjoy discriminating between the one and the lower-case l.
subroutine hpsort(n,b)
integer b(500),bstar
n1=n
l=1+n/2
11 l=l-1
bstar=b(l)
goto 30
25 bstar=b(n1)
b(n1)=b(1)
29 n1=n1-1
30 l1=l
31 m=2*l1
if(m-n1)32,33,37
32 if(b(m+1).ge.b(m)) m=m+1
33 if(bstar.ge.b(m))goto 37
b(l1)=b(m)
l1=m
goto 31
37 b(l1)=bstar
if(l.gt.1)goto 11
if(n1.ge.2)goto 25
return
end
- colejohnson66 6y agoWhy are only some of the lines numbered, and not all?
- winrid 6y agoBecause those lines are jumped to.
- rileymat2 6y agoI might be showing my age, but we used to number the lines manually, but then we would leave gaps in case we needed to add lines in between.
- a1369209993 6y agoI think the numbered lines are branch destinations, but I can't find a goto 29 in there.
- Someone 6y agoTechnically they aren’t numbered, they have a label. Labels serve as jump targets, have to appear in columns 1-5, must be numeric and all different, and should appear in order, but I don’t think they must. (If they must, https://en.wikipedia.org/wiki/Fortran#Simple_FORTRAN_II_program https://en.wikipedia.org/wiki/Fortran#Simple_FORTRAN_II_prog... is in error. It has label 601 follow label 799) Of note is the statement if(m-n1)32,33,37 That jumps to label 32 if (m-n1) is less than zero, to label 33 if it is zero, and to label 37 if it is larger than zero.
- tom_mellior 6y ago> Of course this is a n^2 sort. Isn't it exponential? An n element sort calls two n-1 element sorts. Each of those calls two n-2 element sorts, and so on. So you get 2^n total calls, if I'm not mistaken. That is also why the page asks if you can beat it with a function of equal length but subexponential runtime.
- tromp 6y agoThe following C-code heap sorts integers t[1]...t[j] in ascending order: for (i = j/2; j > 1; t[l] = k) { if (i) k = t[i--]; else { k = t[j]; t[j--] = t[1]; } for (l = i + 1; (m = l + l) <= j; t[l] = t[m], l = m) { if (m < j && t[m] < t[m+1]) m++; if (t[m] <= k) break; } }
- pwdisswordfish2 6y agoThink of this comment what you will, but to me that is some beautiful code. I love the conciseness. Snobol is a bit like that, too. Languages today tend to be relatively verbose, but certainly not as economic nor efficient.