How Many Swaps Can Bubble Sort Take for Six Items?

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

 

[STEMucator]

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)

 

[phospho]

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]

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

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