The worst sort algorithm in the world!

2006-12-31T14:58:00.000-08:00

In interviewing candidates for programming jobs we have tried to come up with some unusual technical questions. Mostly this is to observe the person's reaction to such a question and to see how they might try to solve the problem.

My latest favorite question in this vein is this: "What is the worst sort algorithm you can think of?" The more precise problem definition is that the algorithm must be guaranteed to terminate and that the input will be sorted. Typically bad sort is a bubble sort - whose execution complexity is O(N^2) in the worst case.

But can you do better? Or rather, can you do worse?!

Here is an algorithm that in the worse case is O(N!) - where N! stands for N factorial (i.e. N*(N-1)*(N-2)...2*1). It works like this:

Take random permutation from the set of permutations of N elements
Apply this permutation to the input
If not yet sorted, choose another permutation and go back to previous step

Since there are N! permutations of N elements, on average N!/2 permutations will have to be tried. So the execution complexity of this algorithm will be O(N!).

Just to try it out I wrote this sort in Ruby. Here is the code:


require "permutation"

class Array
  # return true if array is sorted
  def sorted?
    return true if self.length <= 1      
    for i in 0..self.length-2         
      return false if (self[i] > self[i+1])
    end
    true
  end
end

def worst_sort (a)
   perm = Permutation.new(a.length)
   while (perm.rank != perm.last)
      sa = perm.project(a)
      return sa if (sa.sorted?)
      perm.succ!
   end
end

I tried running this sort on my laptop and for an array of 11 elements it was taking so long that I lost patience and stopped the program.

If you look at the code above the most difficult part is generating permutations on N elements in order. I was lucky to find that the hard work was already done for me in the Ruby "permutations" module. You can find the source for this module here: http://permutation.rubyforge.org.

Do you remember your first program?

2006-11-30T16:55:00.000-08:00

The other day we were sitting at lunch reminiscing about how we got started in programming. Every person present had a different story. Here is the story of my first program.

It was the mid-seventies, also known as the Jurasic era of computing, and I was in college taking a physics class. I needed science courses for my future B.S. (Bachelors of Science) degree, so I took physics because I wanted to avoid chemistry. In the physics class we did occsional labs and our professor wanted us to write a computer program to process lab results.

Just to set the stage for the computing technology at the time remember there were no PCs. I had just gotten my first calculator, wich cost $40, not a small sum in the 70s. The calculator had a red LED display and only provided four operations: +, -, * and /. No square root. In fact I learned to use Newton's method to extract square roots by hand. Mind you, my physics professor could do computations and estimates in his head faster than I could type them on my calculator.

In any case after one of the labs, he wrote some gibbrish on the board (starting with "//JOB ") and told us to get some punch cards, and go to the computing center and write and run a program. The program in question was to read seven numbers from its input and print the average. The programming language we were to use was called FORTRAN.

Step one was to buy blank punch cards at the college book store. They were sold in batches of 100. The I had to find the compuer center with the keypunch machines. A kepunch machine was a desk size thing with a typewriter keyboard and an elaborate mechanism for feeding in blank cards. Each letter you typed was encoded in a column of what seem like random holes in the card. If your particular machine had decent printing ribbon in place the character was also shown on the top. The funny thing was that it was hard to see what it was you were typing, so it was easy to make a mistake. Of course, you couldn't fix the card - can't fill in the holes - so a card was wasted and you had to start over.

Once you keypunched you program and the magical control cards that went in front of it, you brought your deck to the RJE - Remote Job Entry - station and handed your card deck though a window to a student employed at the computer center to be read in. He or she would do it immediately and hand you your deck back. The computer would attempt to run job later. The output, a folded print out, would be put on some shelves when it eventually came out.

Nobody told me that if you make a mistake in the control cards (JCL JOB card for you old timers) no output will be generated. So after having my deck read in I hanged out around the computer center wating for results. When nothig came out after what seemed like a reasonable time, I asked for help from one of the local "hackers". He quickly identified my JCL error and told me how to fix it.

This eventually worked and I got my first program to run and print out a weird looking answer (things like: 000102E02 or some such).

So, what was your first program?

Musings on Technology

The worst sort algorithm in the world!

Do you remember your first program?