1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Bubble-sort algorithm

  1. Jul 13, 2012 #1
    Q: Find the maximum number of interchanges needed to sort a list of six pieces of data using the bubble-sort algorithm


    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?
  2. jcsd
  3. Jul 13, 2012 #2


    User Avatar
    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 :

    [itex]\sum_{k=1}^{n-1}[/itex] (n-k)
  4. Jul 13, 2012 #3

    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.
  5. Jul 13, 2012 #4


    User Avatar
    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 (Text):

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook