bubble-sort algorithm

phospho

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?

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 :

[itex]\sum_{k=1}^{n-1}[/itex] (n-k)

phospho

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.

rcgldr

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

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