Algorithms

Just today I implemented bubble sort in Javascript to speed up the inner loop of a search algorithm. I think that's the first time I've actually implemented a sorting algorithm for real in spite of having read pages and pages about them. It's just one of the things that all real programming environments solved long before my time.

Of course, right after having implemented the bubble sort thing, I read on Wikipedia that it's actually considered inferior to insertion sort. So I then switched to insertion sort (I'm only sorting short sequences so asymptotic performance is irrelevant). It's my lucky day, two classic algorithms in such a short span of time...

The simple optimisation work did improve the running time by more than 400%, so that's cool.

When I think of algorithms I invariably come to think of the Knuth–Morris–Pratt algorithm, an algorithm for searching for occurrences of a search phrase in a larger text. A very famous string searching algorithm because it seems clever in theory and with toy examples. Your standard text book on algorithms probably does not mention this, but in practice it is not really an improvement over the simplest possible algorithm, because the issue it is trying to optimise, repeated examinations of the same character, almost never occurs when searching in natural language texts.

I found this out as an undergraduate when we were curious how KMP and the Boyer-Moore algorithm would stack up in practice. We discovered that KMP was only a 1% improvement in the number of characters compared, compared to the simple algorithm.

It's probably a great algorithm for searching DNA strings, though.

I added a note to the Wikipedia page. If I should die tomorrow, please consider it my contribution to the field of computer science.