“Tomato plants” sorting algorithm

By | 2007-06-17

Yesterday I was trying to program a Heapsort algorithm in C, just as a practice to remember how C was (as rough and pure as I remembered). It’s an interesting sorting algorithm, which doesn’t use extra memory, and has a good time complexity, O(n log n). In theory it is as good as the popular Quicksort, but it does have a weird behaviour with almost ordered lists (unsorting the items and resorting them later), using more time than Quicksort uses. This is the reason for its short popularity.

This behaviour has induced me to think about similarities between computer algorithms and nature algorithms. Some algorithms have somehow an inspiration from nature, like the Bubble sort which, as its name suggests, imitates bubbles inside a liquid. Others don’t reflect nature, and this maybe is not too good.

New plants growingI have a lot of tomato plants growing on my balcony. There are too many small plants. Some of them will grow quicker, stealing the soil’s energy from others. Some will not have enough energy to develop. Natural selection. Energy movements, randomness, and quicker first states remind me of something like Simulated annealing. It’s not a honest algorithm, meaning its result is not perfect, and maybe some items get better positions that they should. But it’s an interesting path to develop…

“Part of the inhumanity of the computer is that,
once it is competently programmed and working smoothly,
it is completely honest.”
Isaac Asimov

P.S: … or maybe I must keep my mind disconnected on Sunday morning, and spend the time watching some brilliant animated shorts.