Bubble-sort algorithm

  • Thread starter phospho
  • Start date
  • #1
251
0
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?
 

Answers and Replies

  • #2
STEMucator
Homework Helper
2,075
140
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)
 
  • #3
251
0
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)
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.
 
  • #4
rcgldr
Homework Helper
8,707
534
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
 

Related Threads on Bubble-sort algorithm

  • Last Post
Replies
5
Views
2K
Replies
2
Views
695
Replies
12
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
23
Views
2K
Replies
0
Views
2K
  • Last Post
Replies
1
Views
8K
Replies
25
Views
2K
Replies
1
Views
5K
Top