Hello,
I got this formula from a data structure book in the bubble sort algorithm.
I know that we are (n-1) * (n times), but why the division by 2?
Can anyone please explain this to me or give the detailed proof for it.
Thank you
Hello,
I got this formula from a data structure book in the bubble sort algorithm.
I know that we are (n-1) * (n times), but why the division by 2?
Can anyone please explain this to me or give the detailed proof for it.
Thank you
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.
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.
(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
.
Assume n=2. Then we have 2-1 = 1 on the left side and 2*1/2 = 1 on the right side.
Denote f(n) = (n-1)+(n-2)+(n-3)+...+1
Now assume we have tested up to n=k. Then we have to test for n=k+1.
on the left side we have k+(k-1)+(k-2)+...+1, so it's f(k)+k
On the right side we then have (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)*k/2 = k*f(k)
So this have to hold for every k, and this concludes the proof.
Here's a proof by induction, considering N
terms, but it's the same for N - 1
:
For N = 0
the formula is obviously true.
Suppose 1 + 2 + 3 + ... + N = N(N + 1) / 2
is true for some natural N
.
We'll prove 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2
is also true by using our previous assumption:
1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2
.
So the formula holds for all N
.
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
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.