(N-1) + (N-2) +...+ 2 + 1
is a sum of N-1 items. Now reorder the items so, that after the first comes the last, then the second, then the second to last, i.e. (N-1) + 1 + (N-2) + 2 +..
. The way the items are ordered now you can see that each of those pairs is equal to N (N-1+1 is N, N-2+2 is N). Since there are N-1 items, there are (N-1)/2 such pairs. So you're adding N (N-1)/2 times, so the total value is N*(N-1)/2
.
Start with the triangle...
*
**
***
****
representing 1+2+3+4 so far. Cut the triangle in half along one dimension...
*
**
* **
** **
Rotate the smaller part 180 degrees, and stick it on top of the bigger part...
**
*
*
**
**
**
Close the gap to get a rectangle.
At first sight this only works if the base of the rectangle has an even length - but if it has an odd length, you just cut the middle column in half - it still works with a half-unit-wide twice-as-tall (still integer area) strip on one side of your rectangle.
Whatever the base of the triangle, the width of your rectangle is (base / 2)
and the height is (base + 1)
, giving ((base + 1) * base) / 2
.
However, my base
is your n-1
, since the bubble sort compares a pair of items at a time, and therefore iterates over only (n-1) positions for the first loop.
Try to make pairs of numbers from the set. The first + the last; the second + the one before last. It means n-1 + 1; n-2 + 2. The result is always n. And since you are adding two numbers together, there are only (n-1)/2 pairs that can be made from (n-1) numbers.
So it is like (N-1)/2 * N.
See triangle numbers.
I know that we are (n-1) * (n times), but why the division by 2?
It's only (n - 1) * n
if you use a naive bubblesort. You can get a significant savings if you notice the following:
After each compare-and-swap, the largest element you've encountered will be in the last spot you were at.
After the first pass, the largest element will be in the last position; after the kth pass, the kth largest element will be in the kth last position.
Thus you don't have to sort the whole thing every time: you only need to sort n - 2 elements the second time through, n - 3 elements the third time, and so on. That means that the total number of compare/swaps you have to do is (n - 1) + (n - 2) + ...
. This is an arithmetic series, and the equation for the total number of times is (n - 1)*n / 2.
Example: if the size of the list is N = 5, then you do 4 + 3 + 2 + 1 = 10 swaps -- and notice that 10 is the same as 4 * 5 / 2.
Sum of arithmetical progression
(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2
This is a pretty common proof. One way to prove this is to use mathematical induction. Here is a link: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With