StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If we consider an array from left to right [LeftMost, ..., RightMost], an insertion sort performs the following procedure for each item:</p> <p><ol> <li>Get the current value i.</li> <li>Get the value j (where j = i-1 in the first iteration, or basically the first element to the left of i). In the first iteration of the while array[i] and array[j] are to consecutive elements. For example, if array = [... 60, 100, 50, ...], and array[i] is 50, then array[j] is 100.</li> <li>If the previous value is greater than the current one, then it swaps the two values. Basically if you had something like [..., 60, 100, 50, ...] before this operation takes place, you will end up with [..., 60, 50, 100, ...]. The idea is that you move each item i left as long as there are elements to the left of it that are lower.</p> <blockquote> <p>This is the key of the sort algorithm. Once you are done processing at item i, you have a sorted array from where it originally was all the way to the beggining (left most).</li> <li>Decrease the value of j by one. and go back to step 1 (In this example, this will lead you to compare 50 and 60 and swap them).</li> </ol> If you take a look at the code carefully, you never get a the point where i >= len(s) (<a href="http://docs.python.org/release/1.5.1p1/tut/range.html" rel="nofollow">range</a> is a function that creates a list, and the value i is not changed inside the loop). You can think of the variable i as an imaginary arrow, pointing to a position in the array that has all sorted elements to its left. The variable j simply moves to the left with i fixed, to swap the original array[i] value until it finds another value that is equal or lower than it.</p> </blockquote> <p>Sidenote (not important to understand the algorithm, but could be useful): With that in mind, you can deduce that this algorithm's complexity (measured in worst case comparisons) is O(N^2) where N = len(s). It is similar to having two nested for statements.</p> <p><a href="http://www.youtube.com/watch?v=ROalU379l3U" rel="nofollow">This video</a> does a great job explaining the above, and you know what they say, <em>an image is worth 1000 words</em>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload