Feeding the STEM Myth

The bad thing about this algorithm is that when computers had limited memory, it would cause problems. You would crash the program if you did not have sufficient memory (in this case, at least 4 MB). That was a *big deal* at one time.

This exercise reminds me of why I had to program the heapsort in the first place. More than 20 years ago, I had to rewrite a code that had this algorithm. The program had initially assumed that the numbers would be six digits or less, but later someone changed the input to allow eight-digit numbers (note: not all of the number in this range were used, may 300K to 500K numbers in the list). Well, every time the program started, it tried to allocate ~400 MB of space, causing crashes all over the place. That is when I had to go with something less memory intensive.

Too many think showing up is enough.
Too many think 9-5 is enough.

As someone who backed into the engineering field after 2 decades in manufacturing I can't tell you how astonished this made me. We have 23 year-olds with an excellent salary who have zero work ethic. Then there are others who seem bright enough and seem to try but they can't ever seem to get anything done. In my experience I'd say it take 3-4 hires (hires not applicants) to get a capable engineer.

If you've been around long enough, of course, you have stories like Dilbert and Wally's exchange:

Dilbert: Programmers these days with their object oriented languages. When I started coding we did everything in assembler.
Wally: Hah! Assembler?! We coded everything in 0's and 1's, and sometimes we didn't even have the ones.

My own version of the sort story: In 1979 I'm trying to help a guy who has a sort of 56,000 customer names and addresses running on external disk; system core 64K, user core was only 36K. The whole thing was running on a PDP-8 and took about 70 hours, but it would often crash during that time. [Head skips, power outages, competition with the secretaries during the day time, you name it.] I converted the sort from some guy's entirely disk-based bubble sort [the horrors! the horrors!] to a heap sort that kept the user names and the file pointers to each full address in memory, and ran in about 30K. He was astonished that it finished in about 16 minutes. Today I could run that program, I/O and all, in a few milliseconds.

People do not understand how much of the ancient practice of programming involved working around the limitations of equipment. Just getting a program compiled was a huge deal. My thesis work, all in FORTRAN, was thousands of cards. I remember you had a machine called a "Mod-20" which had no purpose except to list, duplicate, numerate, pre-punch, sort, and perform other punch card-utility functions. My productivity doubled just by having the comp center upgrade from 026 to 029 model keypunch. With the 029, you could prepare a FORTRAN (or COBOL) drum card that automatically skipped to the correct margins, punched continuations in the right columns, and punched consecutive numbers in columns 73-80. A dream come true...

Thanks.

I should point out that I am NOT a professional programmer, and have NEVER taken a course in programming. I am an engineer and self-taught programmer who has written hundreds of one-time-use programs to solve specific engineering problems. I never said they were elegant, only that they worked.

I have written sorting programs using recursion. They are far faster than a bubble sort, which is the obvious way to go about sorting something. Should I ever have to write another sorting program, I'll take a look at your suggestion.

My first reaction after reading the list of problems to be used to test candidate programmers was that I could write a program to do each of them, and do it within the time limit of an employment interview.

It's a horrible thought, but I could probably bluff my way through such an employment interview. Maybe that's why so many massive programs, such as ObamaCare, fail so badly. They're written by people like me, who at best could bluff their way through an employment interview.

Recursion is generally a poor choice. It's a favorite of academics because it teaches a principle of reentrant procedures, but the overhead of pushing the stack frame and context and popping them on return makes it a very expensive operation, particularly for the very short functions -- like a factorial function -- that they routinely use as examples.

It becomes worse on modern hardware because branch prediction is more difficult to do with recursive procedures than it is with do-loop constructs, and flushing the instruction cache invokes a large performance penalty with CPU's that are as fast as those we have now.

The example I gave was a very specific kind of sort. For a general sort, the best answer usually is: use the sort your language or system provides. For general use, it will always be better than anything you can write. But for specific problems a specific answer can be better. In this case, a lot better.

Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.