<p>What algorithm taught you the most about programming or a specific language feature?</p>

<p>We have all had those moments where all of a sudden we know, just know, we have learned an important lesson for the future based on finally understanding an algorithm written by a programmer a couple of steps up the evolutionary ladder.  Whose ideas and code had the magic touch on you?</p>

[{'answer_id': 26321, 'author': 'mk.', 'author_id': 1797, 'author_profile': 'https://Stackoverflow.com/users/1797', 'pm_score': 3, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Quicksort" rel="noreferrer">Quicksort</a>. It showed me that recursion can be powerful and useful. </p>\n'}, {'answer_id': 26324, 'author': 'sparkes', 'author_id': 269, 'author_profile': 'https://Stackoverflow.com/users/269', 'pm_score': 1, 'selected': False, 'text': '<p>This is a slow one :)</p>\n\n<p>I learned lots about both C and computers in general by understanding <a href="http://en.wikipedia.org/wiki/Duff%27s_device" rel="nofollow noreferrer">Duffs Device</a> and <a href="http://en.wikipedia.org/wiki/XOR_swap_algorithm" rel="nofollow noreferrer">XOR swaps</a></p>\n\n<p>EDIT:</p>\n\n<p>@<a href="https://stackoverflow.com/questions/26301/your-favourite-algorithm-and-the-lesson-it-taught-you#26342">Jason Z</a>, that\'s my XOR swap :) cool isn\'t it.</p>\n'}, {'answer_id': 26337, 'author': 'AnnanFay', 'author_id': 2118, 'author_profile': 'https://Stackoverflow.com/users/2118', 'pm_score': 5, 'selected': True, 'text': '<p>"To iterate is human, to recurse divine" - quoted in 1989 at college. </p>\n\n<p>P.S. Posted by Woodgnome while waiting for invite to join</p>\n'}, {'answer_id': 26342, 'author': 'Jason Z', 'author_id': 2470, 'author_profile': 'https://Stackoverflow.com/users/2470', 'pm_score': 2, 'selected': False, 'text': "<p>I don't know if this qualifies as an algorithm, or just a classic hack.  In either case, it helped to get me to start thinking outside the box.</p>\n\n<p>Swap 2 integers without using an intermediate variable (in C++)</p>\n\n<pre><code>void InPlaceSwap (int&amp; a, int &amp;b) {\n     a ^= b;\n     b ^= a;\n     a ^= b;\n}\n</code></pre>\n"}, {'answer_id': 26374, 'author': 'Baltimark', 'author_id': 1179, 'author_profile': 'https://Stackoverflow.com/users/1179', 'pm_score': 0, 'selected': False, 'text': "<p>For me, the simple swap in Kelly &amp; Pohl's <em>A Book on C</em> to demonstrate call-by-reference flipped me out when I first saw it. I looked at that, and pointers snapped into place. Verbatim. . .</p>\n\n<pre><code>void swap(int *p, int *q)\n{\n   int temp;\n\n   temp = *p;\n   *p = *q;\n   *q = temp;\n}\n</code></pre>\n"}, {'answer_id': 26390, 'author': 'Krishna Kumar', 'author_id': 2141, 'author_profile': 'https://Stackoverflow.com/users/2141', 'pm_score': 0, 'selected': False, 'text': '<p>The <a href="http://en.wikipedia.org/wiki/Tower_of_Hanoi" rel="nofollow noreferrer">Towers of Hanoi algorithm</a> is one of the most beautiful algorithms. It shows how you can use recursion to solve a problem in a much more elegant fashion than the iterative method.</p>\n\n<p>Alternatively, the recursion algorithm for Fibonacci series and calculating powers of a number demonstrate the reverse situation of recursive algorithm being used for the sake of recursion instead of providing good value.</p>\n'}, {'answer_id': 26397, 'author': 'OysterD', 'author_id': 2638, 'author_profile': 'https://Stackoverflow.com/users/2638', 'pm_score': 5, 'selected': False, 'text': '<p>General algorithms:</p>\n\n<ul>\n<li>Quicksort (and it\'s average complexity analysis), shows that randomizing your input can be a good thing!;</li>\n<li>balanced trees (<a href="http://en.wikipedia.org/wiki/AVL_tree" rel="noreferrer">AVL trees</a> for example), a neat way to balance search/insertion costs;</li>\n<li><a href="http://en.wikipedia.org/wiki/Dijkstra&#39;s_algorithm" rel="noreferrer">Dijkstra</a> and <a href="http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm" rel="noreferrer">Ford-Fulkerson</a> algorithms on graphs (I like the fact that the second one has many applications);</li>\n<li>the LZ* family of compression algorithms (<a href="http://en.wikipedia.org/wiki/LZW" rel="noreferrer">LZW</a> for example), data compression sounded kind of magic to me until I discovered it (a long time ago :) );</li>\n<li>the <a href="http://en.wikipedia.org/wiki/Fft" rel="noreferrer">FFT</a>, ubiquitous (re-used in so many other algorithms);</li>\n<li>the <a href="http://en.wikipedia.org/wiki/Simplex" rel="noreferrer">simplex</a> algorithm, ubiquitous as well.</li>\n</ul>\n\n<p>Numerical related:</p>\n\n<ul>\n<li>Euclid\'s algorithm to compute the gcd of two integers: one of the first algorithms, simple and elegant, powerful, has lots of generalizations;</li>\n<li>fast multiplication of integers (<a href="http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm" rel="noreferrer">Cooley-Tukey</a> for example);</li>\n<li>Newton iterations to invert / find a root, a very powerful meta-algorithm.</li>\n</ul>\n\n<p>Number theory-related:</p>\n\n<ul>\n<li><a href="http://en.wikipedia.org/wiki/Arithmetic-geometric_mean" rel="noreferrer">AGM</a>-related algorithms (<a href="http://en.wikipedia.org/wiki/Gauss-Legendre_algorithm" rel="noreferrer">examples</a>): leads to very simple and elegant algorithms to compute pi (and much more!), though the theory is quite profound (Gauss introduced elliptic functions and modular forms from it, so you can say that it gave birth to algebraic geometry...);</li>\n<li>the <a href="http://en.wikipedia.org/wiki/Number_field_sieve" rel="noreferrer">number field sieve</a> (for integer factorization): <em>very</em> complicated, but quite a nice theoretical result (this also goes for the <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="noreferrer">AKS</a> algorithm, which proved that PRIMES is in P).</li>\n</ul>\n\n<p>I also enjoyed studying quantum computing (<a href="http://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="noreferrer">Shor</a> and <a href="http://en.wikipedia.org/wiki/Deutsch-Jozsa_algorithm" rel="noreferrer">Deutsch-Josza</a> algorithms for example): this teaches you to think out of the box.</p>\n\n<p>As you can see, I\'m a bit biased towards maths-oriented algorithms :)</p>\n'}, {'answer_id': 26407, 'author': 'Owen', 'author_id': 2109, 'author_profile': 'https://Stackoverflow.com/users/2109', 'pm_score': 1, 'selected': False, 'text': "<p>For some reason Bubble Sort has always stood out to me.  Not because it's elegant or good just because it had/has a goofy name I suppose.</p>\n"}, {'answer_id': 26460, 'author': 'callingshotgun', 'author_id': 2876, 'author_profile': 'https://Stackoverflow.com/users/2876', 'pm_score': 2, 'selected': False, 'text': '<p>The iterative algorithm for Fibonacci, because for me it nailed down the fact that the most elegant code (in this case, the recursive version) is not necessarily the most efficient.</p>\n\n<p>To elaborate-  The "fib(10) = fib(9) + fib(8)" approach means that fib(9) will be evaluated to fib(8) + fib(7).  So evaluation of fib(8) (and therefor fib7, fib6) will all be evaluated twice.</p>\n\n<p>The iterative method, (curr = prev1 + prev2 in a forloop) does not tree out this way, nor does it take as much memory since it\'s only 3 transient variables, instead of n frames in the recursion stack.</p>\n\n<p>I tend to strive for simple, elegant code when I\'m programming, but this is the algorithm that helped me realize that this isn\'t the end-all-be-all for writing good software, and that ultimately the end users don\'t care how your code looks.</p>\n'}, {'answer_id': 26584, 'author': 'Autodidact', 'author_id': 2051, 'author_profile': 'https://Stackoverflow.com/users/2051', 'pm_score': 3, 'selected': False, 'text': '<p>This one might sound trivial but it was a revelation for me at the time.\nI was in my very first programming class(VB6) and the Prof had just taught us about random numbers and he gave the following instructions: "Create a virtual lottery machine. Imagine a glass ball full of 100 ping pong balls marked 0 to 99. Pick them randomly and display their number until they have all been selected, no duplicates."</p>\n\n<p>Everyone else wrote their program like this: Pick a ball, put its number into an "already selected list" and then pick another ball. Check to see if its already selected, if so pick another ball, if not put its number on the "already selected list" etc....</p>\n\n<p>Of course by the end they were making hundreds of comparisons to find the few balls that had not already been picked. It was like throwing the balls back into the jar after selecting them. My revelation was to throw balls away after picking. </p>\n\n<p>I know this sounds mind-numbingly obvious but this was the moment that the "programming switch" got flipped in my head. This was the moment that programming went from trying to learn a strange foreign language to trying to figure out an enjoyable puzzle. And once I made that mental connection between programming and fun there was really no stopping me.</p>\n'}, {'answer_id': 28093, 'author': 'Bruce Alderman', 'author_id': 311, 'author_profile': 'https://Stackoverflow.com/users/311', 'pm_score': 2, 'selected': False, 'text': '<p>Quicksort: Until I got to college, I had never questioned whether brute force Bubble Sort was the most efficient way to sort. It just seemed intuitively obvious. But being exposed to non-obvious solutions like Quicksort taught me to look past the obvious solutions to see if something better is available.</p>\n'}, {'answer_id': 28113, 'author': 'DrPizza', 'author_id': 2131, 'author_profile': 'https://Stackoverflow.com/users/2131', 'pm_score': 1, 'selected': False, 'text': "<blockquote>\n<p>The iterative algorithm for Fibonacci, because for me it nailed down the fact that the most elegant code (in this case, the recursive version) is not necessarily the most efficient.</p>\n<p>The iterative method, (curr = prev1 + prev2 in a forloop) does not tree out this way, nor does it take as much memory since it's only 3 transient variables, instead of n frames in the recursion stack.</p>\n</blockquote>\n<p>You know that fibonacci has a closed form solution that allows direct computation of the result in a fixed number of steps, right?  Namely, (phi<sup>n</sup> - (1 - phi)<sup>n</sup>) / sqrt(5).  It always strikes me as somewhat remarkable that this should yield an integer, but it does.</p>\n<p>phi is the golden ratio, of course; (1 + sqrt(5)) / 2.</p>\n"}, {'answer_id': 28118, 'author': 'wusher', 'author_id': 1632, 'author_profile': 'https://Stackoverflow.com/users/1632', 'pm_score': 2, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Minimax" rel="nofollow noreferrer">Minimax</a> taught me that chess programs aren\'t smart, they can just think more moves ahead than you can. </p>\n'}, {'answer_id': 28122, 'author': 'Mat Noguchi', 'author_id': 1799, 'author_profile': 'https://Stackoverflow.com/users/1799', 'pm_score': 0, 'selected': False, 'text': '<p>@Krishna Kumar</p>\n\n<p>The bitwise solution is even more fun than the recursive solution.</p>\n'}, {'answer_id': 28127, 'author': 'Lasse V. Karlsen', 'author_id': 267, 'author_profile': 'https://Stackoverflow.com/users/267', 'pm_score': 3, 'selected': False, 'text': '<p>Huffman coding would be mine, I had originally made my own dumb version by minimizing the number of bits to encode text from 8 down to less, but had not thought about variable number of bits depending on frequency. Then I found the huffman coding described in an article in a magazine and it opened up lots of new possibilities.</p>\n'}, {'answer_id': 28138, 'author': 'Pat', 'author_id': 238, 'author_profile': 'https://Stackoverflow.com/users/238', 'pm_score': 2, 'selected': False, 'text': '<p>For some reason I like the <a href="http://en.wikipedia.org/wiki/Schwartzian_transform" rel="nofollow noreferrer">Schwartzian transform</a></p>\n\n<pre><code>@sorted = map  { $_-&gt;[0] }\n          sort { $a-&gt;[1] cmp $b-&gt;[1] }\n          map  { [$_, foo($_)] }\n                @unsorted;\n</code></pre>\n\n<p>Where foo($<em>) represents a compute-intensive expression that takes $</em> (each item of the list in turn) and produces the corresponding value that is to be compared in its sake.</p>\n'}, {'answer_id': 28145, 'author': 'Alexander Stolz', 'author_id': 2450, 'author_profile': 'https://Stackoverflow.com/users/2450', 'pm_score': 2, 'selected': False, 'text': "<p>Quicksort in Haskell:</p>\n\n<pre><code>qsort []     = []\nqsort (x:xs) = qsort (filter (&lt; x) xs) ++ [x] ++ qsort (filter (&gt;= x) xs)\n</code></pre>\n\n<p>Although I couldn'd write Haskell at the time, I did understand this code and with it recursion and the quicksort algorithm. It just made click and there it was...</p>\n"}, {'answer_id': 39693, 'author': 'spoulson', 'author_id': 3347, 'author_profile': 'https://Stackoverflow.com/users/3347', 'pm_score': 3, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm" rel="noreferrer">Bresenham\'s line drawing algorithm</a> got me interested in realtime graphics rendering.  This can be used to render filled polygons, like triangles, for things like 3D model rendering.</p>\n'}, {'answer_id': 39793, 'author': 'Henry', 'author_id': 3598, 'author_profile': 'https://Stackoverflow.com/users/3598', 'pm_score': 3, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Recursive_descent_parser" rel="noreferrer">Recursive Descent Parsing</a> - I remember being very impressed how such simple code could do something so seemingly complex. </p>\n'}, {'answer_id': 320417, 'author': 'Daniel Rikowski', 'author_id': 23368, 'author_profile': 'https://Stackoverflow.com/users/23368', 'pm_score': 2, 'selected': False, 'text': '<p>For me it\'s the weak-heapsort algorithm because it shows (1) how much a wise chosen data structure (and the algorithms working on it) can influence the performance and (2) that fascinating things can be discovered even in old, well-known things. (weak-heapsort is the best variant of all heap sorts, which was <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1863" rel="nofollow noreferrer">proven</a> eight years later.)</p>\n'}, {'answer_id': 320881, 'author': 'J.T. Hurley', 'author_id': 39851, 'author_profile': 'https://Stackoverflow.com/users/39851', 'pm_score': 0, 'selected': False, 'text': "<p>An algorithm that generates a list of primes by comparing each number to the current list of primes, adding it if it's not found, and returning the list of primes at the end. Mind-bending in several ways, not the least of which being the idea of using the partially-completed output as the primary search criteria.</p>\n"}, {'answer_id': 440125, 'author': 'blabla999', 'author_id': 48469, 'author_profile': 'https://Stackoverflow.com/users/48469', 'pm_score': 0, 'selected': False, 'text': '<p>Storing two pointers in a single word for a doubly linked list tought me the lesson that you can do very bad things in C indeed (with which a conservative GC will have lots of trouble).</p>\n'}, {'answer_id': 1538350, 'author': 'Dean J', 'author_id': 182690, 'author_profile': 'https://Stackoverflow.com/users/182690', 'pm_score': 0, 'selected': False, 'text': "<p>The most proud I've been of a solution was writing something very similar to the DisplayTag package.  It taught me a lot about code design, maintainability, and reuse.  I wrote it well before DisplayTag, and it was sunk into an NDA agreement, so I couldn't open source it, but I can still speak gushingly about that one in job interviews.</p>\n"}, {'answer_id': 1538360, 'author': 'sykora', 'author_id': 53850, 'author_profile': 'https://Stackoverflow.com/users/53850', 'pm_score': 0, 'selected': False, 'text': '<p>Not my favorite, but the <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow noreferrer">Miller Rabin Algorithm</a> for testing primality showed me that being right almost all the time, is good enough almost all the time. (i.e. Don\'t mistrust a probabilistic algorithm just because it has a probability of being wrong.)</p>\n'}, {'answer_id': 1538367, 'author': 'stusmith', 'author_id': 6604, 'author_profile': 'https://Stackoverflow.com/users/6604', 'pm_score': 0, 'selected': False, 'text': '<p>Map/Reduce. Two simple concepts that fit together to make a load of data-processing tasks easier to parallelize.</p>\n\n<p>Oh... and it\'s only the basis of massively-parallel indexing:</p>\n\n<p><a href="http://labs.google.com/papers/mapreduce.html" rel="nofollow noreferrer">http://labs.google.com/papers/mapreduce.html</a></p>\n'}, {'answer_id': 1538371, 'author': 'csl', 'author_id': 21028, 'author_profile': 'https://Stackoverflow.com/users/21028', 'pm_score': 1, 'selected': False, 'text': '<p>I don\'t have a <em>favourite</em> -- there are so many beautiful ones to pick from -- but one I\'ve always found intriguing is the <a href="http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula" rel="nofollow noreferrer">Bailey–Borwein–Plouffe (BBP) formula</a>, which enables you to calculate an arbitrary digit of pi without knowledge about the preceding digits.</p>\n'}, {'answer_id': 2383873, 'author': 'polygenelubricants', 'author_id': 276101, 'author_profile': 'https://Stackoverflow.com/users/276101', 'pm_score': 4, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="noreferrer">Floyd-Warshall all-pairs shortest paths algorithm</a></p>\n\n<pre><code>procedure FloydWarshall ()\n   for k := 1 to n\n     for i := 1 to n\n        for j := 1 to n\n          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );\n</code></pre>\n\n<p>Here\'s why it\'s cool: when you first learn about the shortest-path problem in your graph theory course, you probably start with Dijkstra\'s algorithm that solves <strong>single</strong>-source shortest path. It\'s quite complicated at first, but then you get over it, and you fully understood it.</p>\n\n<p>Then the teacher says "Now we want to solve the same problem but for <strong>ALL</strong> sources". You think to yourself, "Oh god, this is going to be a much harder problem! <em>It\'s going to be at least N times more complicated than Dijkstra\'s algorithm!!!</em>".</p>\n\n<p>Then the teacher gives you Floyd-Warshall. And your mind explodes. Then you start to tear up at how beautifully simple the algorithm is. It\'s just a triply-nested loop. It only uses a simple array for its data structure.</p>\n\n<hr>\n\n<p>The most eye-opening part for me is the following realization: say you have a solution for problem A. Then you have a bigger "superproblem" B which contains problem A. The solution to problem B may in fact be simpler than the solution to problem A.</p>\n'}, {'answer_id': 3470289, 'author': 'BlueRaja - Danny Pflughoeft', 'author_id': 238419, 'author_profile': 'https://Stackoverflow.com/users/238419', 'pm_score': 1, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/RSA" rel="nofollow noreferrer">RSA</a> introduced me to the world of modular arithmetic, which can be used to <a href="http://en.wikipedia.org/wiki/Diffie-Hellman" rel="nofollow noreferrer">solve</a> <a href="http://en.wikipedia.org/wiki/Digital_signature" rel="nofollow noreferrer">a</a> <a href="http://en.wikipedia.org/wiki/Blum_blum_shub" rel="nofollow noreferrer">surprising</a> <a href="http://en.wikipedia.org/wiki/Oblivious_transfer" rel="nofollow noreferrer">number</a> <a href="http://en.wikipedia.org/wiki/Anonymous_internet_banking" rel="nofollow noreferrer">of</a> <a href="http://en.wikipedia.org/wiki/Zero_knowledge_proof" rel="nofollow noreferrer">interesting</a> <a href="http://en.wikipedia.org/wiki/Secret_Sharing_using_the_Chinese_Remainder_Theorem" rel="nofollow noreferrer">problems</a>!</p>\n'}, {'answer_id': 13854383, 'author': 'maasha', 'author_id': 764601, 'author_profile': 'https://Stackoverflow.com/users/764601', 'pm_score': 0, 'selected': False, 'text': '<p>Binary search must be the most simple and elegant algorithm. Of cause the data needs to be sorted and for this the merge sort algorithm is also most simple and elegant.</p>\n'}, {'answer_id': 13854456, 'author': 'Anti Earth', 'author_id': 848292, 'author_profile': 'https://Stackoverflow.com/users/848292', 'pm_score': 1, 'selected': False, 'text': '<p>Hasn\'t taught me much, but the <a href="http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm" rel="nofollow">Johnson–Trotter Algorithm</a> never fails to blow my mind.</p>\n'}, {'answer_id': 13857202, 'author': 'maxim1000', 'author_id': 155783, 'author_profile': 'https://Stackoverflow.com/users/155783', 'pm_score': 0, 'selected': False, 'text': '<ol>\n<li>Using matrix arithmetic for computing Fibonacci in O(log N)</li>\n<li>Using Fourier transform for big numbers multiplication</li>\n</ol>\n\n<p>The lesson is that a solution can be found in very unexpected areas and that there are very surprising connections between different areas of algorithms and mathematics.</p>\n'}, {'answer_id': 16318867, 'author': 'solendil', 'author_id': 760641, 'author_profile': 'https://Stackoverflow.com/users/760641', 'pm_score': 0, 'selected': False, 'text': '<p>Some algorithms, principles or tricks that have not yet been cited:</p>\n\n<ul>\n<li><a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow">Union-Find</a> algorithm to quickly extract groups from a dataset.</li>\n<li><a href="http://en.wikipedia.org/wiki/Zobrist_hashing" rel="nofollow">Zobrist hashcodes</a> are quick, iterative and resilient to collisions.</li>\n<li><a href="http://en.wikipedia.org/wiki/Constraint_programming" rel="nofollow">Constraint programming</a> is a programming paradigm that leads to surprising good results in a variety of cases.</li>\n<li><a href="https://www.google.fr/search?q=monte%20carlo%20tree%20search&amp;aq=f&amp;oq=monte%20carlo%20tree%20search&amp;aqs=chrome.0.57j0l3.3749j0&amp;sourceid=chrome&amp;ie=UTF-8" rel="nofollow">Monte Carlo tree search</a> is a set of wonderful techniques mixing tree walking, randomization, optimization.</li>\n</ul>\n'}, {'answer_id': 16320624, 'author': 'wildplasser', 'author_id': 905902, 'author_profile': 'https://Stackoverflow.com/users/905902', 'pm_score': 1, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Binary_decision_diagrams" rel="nofollow">Binary decision diagrams</a>, though formally not an algorithm but a datastructure, lead to elegant and minimal solutions for various sorts of (boolean) logic problems. They were invented and developped to minimise the gate count in chip-design, and can be viewed as one of the fundaments of the silicon revolution. The resulting algorithms are amazingly simple.</p>\n\n<p>What they taught me:</p>\n\n<ul>\n<li>a compact representation of <em>any</em> problem is important; small is beautiful</li>\n<li>a small set of constraints/reductions applied recursively can be used to accomplish this</li>\n<li>for problems with symmetries, tranformation to a canonical form should be the first step to consider</li>\n<li>not every piece of literature is read. Knuth found out about BDD\'s several years after their invention/introduction. (and spent almost a year investigating them)</li>\n</ul>\n'}]
['https://Stackoverflow.com/questions/26301', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/269/']