## bubble-sort algorithm

Q: Find the maximum number of interchanges needed to sort a list of six pieces of data using the bubble-sort algorithm

working:

for the first past, maximum needed is n-1 swaps where n is the amount of the pieces of data
2nd - n-2
3rd - n-3
4th - n-4
5th - n-5

so generally it takes

(n-1) + (n-2) +... (n-(n-1))

is this correct? It works for six as the it will be a maximum of 15 swaps, also how can I generalise this?
 PhysOrg.com science news on PhysOrg.com >> Galaxies fed by funnels of fuel>> The better to see you with: Scientists build record-setting metamaterial flat lens>> Google eyes emerging markets networks
 This would be more suitable for the computer science section, but hey ill help. Consider an array of natural numbers ( I'll be using some java syntax here to provide a practical example ) : int[] nums = {0,1,2,3,4,5,...n}; and presume you want to sort it from highest to lowest ( So we have a worst case scenario here ). There are n elements in the array, so to move 0 to the nth position would require n-1 exchanges. The next exchange for 1 would require n-2 exchanges. This continues until you have n-(n-1) exchanges since n-n would be redundant because the list is sorted at that point. I suppose a way you could generalize this would be to say : $\sum_{k=1}^{n-1}$ (n-k)

 Quote by Zondrina This would be more suitable for the computer science section, but hey ill help. Consider an array of natural numbers ( I'll be using some java syntax here to provide a practical example ) : int[] nums = {0,1,2,3,4,5,...n}; and presume you want to sort it from highest to lowest ( So we have a worst case scenario here ). There are n elements in the array, so to move 0 to the nth position would require n-1 exchanges. The next exchange for 1 would require n-2 exchanges. This continues until you have n-(n-1) exchanges since n-n would be redundant because the list is sorted at that point. I suppose a way you could generalize this would be to say : $\sum_{k=1}^{n-1}$ (n-k)
Cheers,

btw I had no idea it was the wrong section, in the UK, this is under our maths syllabus and we're not programming anything, but I can see how it leads to things :)

thanks again.

Recognitions:
Homework Help

## bubble-sort algorithm

There's a trick to adding up an incrementing series of numbers, arrange the numbers forwards and backards and add up the sum:

Code:
n-1 + n-2 + n-3 + ... +   1
1 +   2 +   3 _ ... + n-1
---------------------------
n +   n +   n + ... +   n
This sum equals n (n-1), but since the array was added twice divide by 2:

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