Learn the essential functions of CompTIA Security+, which establishes the core knowledge required of any cybersecurity role and leads professionals into intermediate-level cybersecurity jobs.

At 2:05 of this video, they say that in order to do a bubble sort on an array of n elements, first you perform n-1 comparisons, and then you perform n-2 comparisons. I don't understand why the comparisons become fewer and fewer with each round of comparisons. Is it because the biggest number in the array makes it to the end of the array after the first round of comparisons?

http://www.youtube.com/watch?v=P00xJgWzz2c

http://www.youtube.com/watch?v=P00xJgWzz2c

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

If you take a 5 element array, it seems like you would make (n-1)+(n-2)+(n-3)+1 comparisons, which is equal to 3n-5. How did they get n(n-1)/2?

but also

n(n-1)/2 = 5(4)/2 = 10

So they are the same.

For any series 1 + 2 + 3 + 4 + ... + n-1 the sum is n(n-1)/2

Set S = 1 + 2 + 3 + 4 + ... + n-1

So 2S = S + S = 1 + 2 + 3 + 4 + ... + n-1 + 1 + 2 + 3 + 4 + ... + n-1

Put the second S in reverse order and you have

1 + 2 + 3+ ... + n-1

+ n-1 + n-2 + n-3 + ... + 1

= n + n + n + ... + n

And there are n-1 terms in each S. So 2S = n(n-1) so S = n(n-1)/2

S = 3n-5

2S = 7n -14

2S = 7(n-2)

S = 7(n-2)/2

If it's hard to follow, you can just take my word for it, but I can try a different approach.

Again, say S = 1 + 2 + 3 + ... + n-2 + n-1

Take the first (1) and last (n-1) and add them 1 + n-1 = n

Now take the second (2) and second to last (n-2) and add them 2 + n-2 = n

You'll notice that each pair sums to n. Also, since there are n-1 numbers, there will be (n-1)/2 pairs. So the total will be n(n-1)/2

For example for n=7

1 + 2 + 3 + 4 + 5 + 6

rearranges to

1 + 6 + 2 + 5 + 3 + 4

=

(1 + 6) + (2 + 5) + (3 + 4)

=

7 + 7 + 7

= 7(3)

7=n, 3=(n-1)/2

http://www.khanacademy.org/video/alternate-proof-to-induction-for-integer-sum?playlist=Algebra

Tommy said it, but the video just animates it.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialIf you have an array of n elements, you know that in a bubble sort you will make n-1 comparisons in the first round of comparisons. Then in the second round, because the biggest element is already in the last spot, you will only have n-2 comparisons. You continue with fewer comparisons in each round until in the final round of comparisons you only need 1 comparison (the first two elements of the array). So the first formula you see on the

S(n) = (n-1) + (n-2) + (n-3) +... 3 + 2 + 1

2S(n) = n + n + n + ...n + n + n

2S(n) = (n-1)(n)

S(n) = n(n-1)/2

Algorithms

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

Yes

After the first pass, the last entry is the largest element in the array. That means that this last element is in the correct sort position. If there were 100 elements to sort, then after the first pass, there are now only 99 elements to sort.

After the 2nd pass, the two largest elements are at the end of the array, so there are now only 98 elements left to sort.

Less numbers to sort in each pass --> less comparisons in each pass.