[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

In this video what do they mean by n-2?

Posted on 2011-10-05
14
Medium Priority
?
246 Views
Last Modified: 2012-08-14
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
0
Comment
Question by:shampouya
  • 6
  • 4
  • 4
14 Comments
 
LVL 32

Expert Comment

by:phoffric
ID: 36921031
>> Is it because the biggest number in the array makes it to the end of the array after the first round of comparisons?
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.
0
 

Author Comment

by:shampouya
ID: 36921071
Oh ok thanks. And also, why is the sum of the comparison series equal to n(n-1)/2?

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?
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36921109
(n-1)+(n-2)+(n-3)+1 if n is 4 is 4 + 3 + 2 + 1 = 10
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
0
How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36921129
The way you get it is as follows.
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
0
 

Author Comment

by:shampouya
ID: 36921226
Hmmm I lost you on the second line, that was pretty complicated. Is there any way we can derive it with the Sum of 5 elements and the Sum of 6 elements like this?

      S = 3n-5
+    S = 4n-9
  2S = 7n -14
  2S = 7(n-2)
  S = 7(n-2)/2
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36921388
No. You can't derive it that way since the ns are different. In the first line n=5 and in the second n=6. But notice that 3(5)-5 = 10 and 4(6)-9 = 15 and those are the same numbers you get if you use n(n-1)/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
0
 
LVL 32

Accepted Solution

by:
phoffric earned 2000 total points
ID: 36921675
Integer Sum - Here is a 3.5 minute video for your enjoyment:
   http://www.khanacademy.org/video/alternate-proof-to-induction-for-integer-sum?playlist=Algebra

Tommy said it, but the video just animates it.
0
 

Author Comment

by:shampouya
ID: 36922174
That video was perfect, thanks. Tommy, phoffric, in case anyone asks you for an idiot-proof explanation of this in the future, I have provided one below. Let me know what you think:

If 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 first line below for S(n) represents the number of comparisons you can expect from a bubble sort of size n (any size). Now, let's write the same formula for S(n) on the second line, but let's write it backwards. Now add those two formulas together and you will arrive at the third line below. Notice how every sum looks the same, n. You know that all in all, there will be (n -1) rounds of comparisons, so we can simplify the n+n+n+...n+n+n by just writing (n-1)*(n). Now divide each side of the equation by 2, and you get S(n) = n(n-1)/2. That's how many rounds of comparisons you'll have for a bubble sort of an array n-elements long.

S(n)  =  (n-1)  + (n-2)  + (n-3)  +...  3     +  2     + 1
S(n)  =   1      + 2       + 3       +... (n-3) + (n-2) + (n-1)
2S(n) =  n      + n       + n       + ...n      + n      + n
2S(n) = (n-1)(n)
S(n)   = n(n-1)/2
0
 
LVL 32

Expert Comment

by:phoffric
ID: 36922206
Being a devil's advocate, I was going to ask you to defend your view that there will be n-1 comparisons in the first round. But in your 2nd sentence, you actually do provide a good intuitive answer - "you only need 1 comparison (the first two elements of the array)". Well done!
0
 

Author Closing Comment

by:shampouya
ID: 36922231
thanks buddy!
0
 
LVL 32

Expert Comment

by:phoffric
ID: 36922428
Glad to have assisted.

Don't forget that you can split points to contributors that helped.
0
 

Author Comment

by:shampouya
ID: 36922449
I appreciated the other answers but I couldn't understand them! Your video link was perfect.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36926088
Your solution is actually the exact same as my first attempt in http:#a36921129 just formatted a bit better.
0
 

Author Comment

by:shampouya
ID: 36926343
Tommy I'm sure you're a lot smarter than I am, but your solution was very hard to follow for the average person. The reason being, you mentioned 2S before you described what the reverse order of the original S was. Then, you didn't take the first S equation and the reverse-S equation and stack them on top of each other and align them so that it was clear that each element in the series summed up to n. And you also wrote the series as 1 + 2 + 3 +...n-1, when you should have written it as 1 + 2 + 3 +...n-3 + n-2 + n-1, because that makes it easier for the reader to see how the series ends and how it aligns up symmetrically with the reverse form of the series. I also don't think you mentioned the word sum in your solution 36921129 to indicate that the summing of two formulas was occurring. It's probably because you know the material so well that you took for granted some of the things that people like myself aren't clear on. But again, I appreciate your solution, and now that I read it again, it all makes sense!
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Despite its rising prevalence in the business world, "the cloud" is still misunderstood. Some companies still believe common misconceptions about lack of security in cloud solutions and many misuses of cloud storage options still occur every day. …

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question