# 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?

Related Engineering and Comp Sci Homework Help News on Phys.org
STEMucator
Homework Helper
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)

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.

rcgldr
Homework Helper
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