Dijkstra's algorithm ( <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm</a> )<p>It is a really elegant algorithm and addresses a real-world problem. A teacher of mine once showed us the basic idea behind it:<p>He connected various bits of wood (=nodes) using strings (=edges). Then he picked up one bit of wood (=starting node) and slowly moved it upwards. Every time when a new node moves, it is an indication that the shortest path between the start node and the new node has been found. He did this until he reached the desired end node.
The shortest path between the two nodes is in the end clearly visible, because the path between two nodes A and B that are part of the path between the start and end node is always the shortest path possible.<p>It is really simple if you think of it as a physical model, unfortunately I could not find a picture of it online :(
Gale–Shapley algorithm (for the stable marriages problem) <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="nofollow">http://en.wikipedia.org/wiki/Stable_marriage_problem</a><p>It's a beautifully simple algorithm with uses in almost every field.<p>Here's a more informative link <a href="http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-algorithm/" rel="nofollow">http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-a...</a>
My favourite would have to be one that I invented myself. I guess like a lot of people here I occasionally end up having to figure out algorithms to solve particular problems. That is one of the most rewarding aspects of being a programmer.
I don't know that I have favorites. That said, Radix sort is kinda cool. It's O(n * k), where k is the number of digits in the number, but it's possible to have k be a constant if there is a limit (like an int can only be so big) meaning you can have an O(n) sort.
I really dig AI algorithms like...<p><a href="http://www.norvig.com/spell-correct.html" rel="nofollow">http://www.norvig.com/spell-correct.html</a><p>Simplicity is beautiful.
I like the Monte Carlo algorithm: <a href="http://en.wikipedia.org/wiki/Monte_Carlo_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Monte_Carlo_algorithm</a>
Insertion sort. Easy to implement (easier than BubbleSort), very fast for small data sets. Can be used in merge sorts / quick sorts when the set size becomes small.