My bubble sort seems to be running too many times, or running backwards

Question

I am creating a program that prints out all the permutations of a sequence in lexicographical order. One part of the algorithm to do this, requires me to sort out all numbers into Ascending order after the point of where a swap has occurred.

However, my bubble sort seems to be rearranging the wrong numbers, even though it arranges them fine in the first 8 or so runs in the loop. I think it has to do with how many times my loop needs to run, but I can't work out what?

Here is an example of where my sort does not work:

The sequence will be: 2-3-4-1 and it needs to be rearranged as: 2-3-1-4. So after 3 all the numbers need to be rearranged into ascending order. However the output is: 2-1-3-4. Meaning it is rearranging them all after the 2 and not the 1.

Here is my sort:

for(int i=newTrueIndex; i < l; i++)
           {
              for(int j=seenCount+1; j < l; j++)
              {
                 if(seq[j-1] > seq[j])
                 {
                    int temp4=seq[j-1];
                    seq[j-1] = seq[j];
                    seq[j] = temp4; 

                 }
              }

           }

At this point newTrueIndex =1 and seenCount = 1

and the numbers are all stored in seq.

Answer 1

A few notes about the code

• Are you required to use bubble sort? (is this a homework assignment). If not there is java.util.Arrays.sort() method which you can use: java.util.Arrays.sort(seq, newTrueIndex, l)

• My #1 guess is that the value of l is not what you expect it to be.

• j should starting from seeonCount creates a potential point of failure in your code. i and j should iterate over the same range. If your range is starting at newTrueIndex then both variables should start at this value. Adding a second starting point (namely: seenCount) can create problem if the two starting point are not kept in sync.

• j is starting from seenCount that is: a value that represent quantity but is used as an index. a count is equivalent to an index only if indexing starts from 0.