StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Alright, let's think about this. </p> <p>We realize that every number needs to be eventually swapped with every number after it that's less than it, sooner or later. Thus, the total number of swaps for a given number is the total number of numbers after it which are less than it. However, this is still <code>O(n^2)</code> time.</p> <p>For every pass of the outer loop of bubble sort, one element gets put in the correct position. Without loss of generality, we'll say that for every pass, the largest element remaining gets sorted to the end of the list.</p> <p>So, in the first pass of the outer loop, the largest number is put at the end. This takes <em>q</em> swaps, where <em>q</em> is the number of positions the number started away from the final position.</p> <p>Thus, we can say that it will take <em>q<sub>1</sub>+q<sub>2</sub>+ ... +q<sub>n</sub></em> swaps to complete this bubble sort. However, keep in mind that with every swap, one number will be taken either one position closer or one position farther away from their final positions. In our specific case, if a number is in front of a larger number, and at or in front of its correct position, one more swap will be required. However, if a number is behind a larger number and behind it's correct position, one less swap will be required.</p> <p>We can see that this is true with the following example:</p> <pre><code> 5 3 1 2 4 => 3 5 1 2 4 => 3 1 5 2 4 => 3 1 2 5 4 => 3 1 2 4 5 => 1 3 2 4 5 => 1 2 3 4 5 (6 swaps total) </code></pre> <p>"5" moves 4 spaces. "3" moves 1 space. "1" moves 2 spaces. "2" moves 2 spaces. "4" moves 1 space. Total: 10 spaces.</p> <p>Note that 3 is behind 5 and in front of its correct position. Thus one more swap will be needed. 1 and 2 are behind 3 and 5 -- four less swaps will be needed. 4 is behind 5 and behind its correct position, thus one less swap will be needed. We can see now that the expected value of 6 matches the actual value.</p> <p>We can compute Σ<em>q</em> by sorting the list first, keeping the original positions of each of the elements in memory while doing the sort. This is possible in <code>O(nlogn + n)</code> time.</p> <p>We can also see what numbers are behind what other numbers, but this is impossible to do in faster than <code>O(n^2)</code> time. However, we can get a faster solution.</p> <p>Every swap effectively moves two numbers number needs to their correct positions, but some swaps actually do nothing, because one be eventually swapped with every number gets closerafter it that's less than it, and another gets farthersooner or later. The first swap in our previous exampleThus, between "3" and "5" is the only example of this in our example.</p> <p>We have to calculate how many total number of said swaps that there are. This is left as an exercise to the reader, but here's one last hint: you only have to loop through the first half of the list. Though this for a given number is still, in the end <code>O(n^2)</code>, we only have to do <code>O(n^2)</code> operations on the first half total number of the list, making numbers after it much faster overall.</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