How to debug my Bubble Sort code?

Question

I got this bubblesort in college and am trying to run it! It's supposed to sort the numbers in order of size, smallest to largest. Any help would be appreciated. (It comes from Derek Banas on YouTube). Do you know why it doesn't work?

public class ListForSorting {

    int arraySize = 10;
    int[] myArray = { 10, 12, 3, 4, 50, 60, 7, 81, 9, 100 };

    public void printArray() {

        System.out.println("----------");
        for (int i = 0; i < arraySize; i++) {

            System.out.print("| " + i + " | ");
            System.out.println(myArray[i] + " |");

            System.out.println("----------");

        }

    }

    public static void main(String[] args) {
        ListForSorting list = new ListForSorting();

        list.printArray();

        list.bubbleSort();
        list.printArray();
    }

    public void bubbleSort() {

        for (int i = arraySize - 1; i > 1; i--) {
            for (int j = 0; j < i; j++) {
                if (myArray[j] < myArray[j + 1])
                    swap(j, j + 1);

            }
        }

    }

    public void swap(int indexOne, int indexTwo) {
        int temp = myArray[indexOne];
        myArray[indexOne] = myArray[indexTwo];
        temp = myArray[indexTwo];
    }
}

Output:

----------
| 0 | 10 |
----------
| 1 | 12 |
----------
| 2 | 3 |
----------
| 3 | 4 |
----------
| 4 | 50 |
----------
| 5 | 60 |
----------
| 6 | 7 |
----------
| 7 | 81 |
----------
| 8 | 9 |
----------
| 9 | 100 |
----------
----------
| 0 | 81 |
----------
| 1 | 100 |
----------
| 2 | 100 |
----------
| 3 | 100 |
----------
| 4 | 100 |
----------
| 5 | 100 |
----------
| 6 | 100 |
----------
| 7 | 100 |
----------
| 8 | 100 |
----------
| 9 | 100 |

Thanks!

Answer 1

Your swap function was wrong. It should be like this:

public void swap(int indexOne, int indexTwo) {
    int temp = myArray[indexOne];
    myArray[indexOne] = myArray[indexTwo];
    myArray[indexTwo] = temp;
}

Also, bubblesort function has an error. Counter i should go down to 1 not to 2, or else your first element wont be sorted as it should be:

public void bubbleSort() {

        for (int i = arraySize - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (myArray[j] < myArray[j + 1])
                    swap(j, j + 1);

            }
        }

    }

Now it outputs:

----------
| 0 | 10 |
----------
| 1 | 12 |
----------
| 2 | 3 |
----------
| 3 | 4 |
----------
| 4 | 50 |
----------
| 5 | 60 |
----------
| 6 | 7 |
----------
| 7 | 81 |
----------
| 8 | 9 |
----------
| 9 | 100 |
----------
----------
| 0 | 100 |
----------
| 1 | 81 |
----------
| 2 | 60 |
----------
| 3 | 50 |
----------
| 4 | 12 |
----------
| 5 | 10 |
----------
| 6 | 9 |
----------
| 7 | 7 |
----------
| 8 | 4 |
----------
| 9 | 3 |
----------

If you want from smallest number to biggest, just change if condition in bubblesort function:

public void bubbleSort() {

        for (int i = arraySize - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (myArray[j] > myArray[j + 1])
                    swap(j, j + 1);

            }
        }

    }

Now, the output would be:

----------
| 0 | 10 |
----------
| 1 | 12 |
----------
| 2 | 3 |
----------
| 3 | 4 |
----------
| 4 | 50 |
----------
| 5 | 60 |
----------
| 6 | 7 |
----------
| 7 | 81 |
----------
| 8 | 9 |
----------
| 9 | 100 |
----------
----------
| 0 | 3 |
----------
| 1 | 4 |
----------
| 2 | 7 |
----------
| 3 | 9 |
----------
| 4 | 10 |
----------
| 5 | 12 |
----------
| 6 | 50 |
----------
| 7 | 60 |
----------
| 8 | 81 |
----------
| 9 | 100 |
----------

Edit: performance

You can make this faster by "checking" if inner loop did at least one swap. If it didn't that means you can exist the outer loop since it finished and save time for the rest of outer loop iteration.

Answer 2

You got few problems in your code the most problematic are:

1. wrong swap (last line should be reversed)

2. you are looping the whole thing N-1 times

   that is needlessly too much loop only until array is sorted instead. So until no swap occurs in the inner loop.

I code ascending Bubble sort like this (in C++):

void sort_asc(int *a,int n)
    {
    int i,e;
    for (e=1;e;n--)                 // loop until no swap occurs
     for (e=0,i=1;i<n;i++)          // process array
      if (a[i-1]>a[i])              // if swap needed
       {
       e=a[i-1];                    // swap
       a[i-1]=a[i];
       a[i]=e;
       e=1;                         // allow to process array again
       }
    }

usage:

int a[]={ 9,8,7,6,5,4,3,2,1,0 };    // worse case scenario
sort_asc(a,sizeof(a)/sizeof(a[0]));

Descending order is just matter of changing condition to:

      if (a[i-1]<a[i])              // if swap needed

btw here some measurements of sorting 32bit int a[1024] arrays looped 100 times:

                         Time        Space

[   1.428 ms] Worse case O(n)
[ 312.744 ms] Bubble asc O(n^2)      O(1     ) OK
[ 306.084 ms] Bubble dsc O(n^2)      O(1     ) OK
[   9.883 ms] Quick  asc O(n.log(n)) O(log(n)) OK
[  10.620 ms] Quick  dsc O(n.log(n)) O(log(n)) OK

[   1.816 ms] Random     O(n)
[ 374.343 ms] Bubble asc O(n^2)      O(1     ) OK
[ 361.219 ms] Bubble dsc O(n^2)      O(1     ) OK
[  14.402 ms] Quick  asc O(n.log(n)) O(log(n)) OK
[  14.519 ms] Quick  dsc O(n.log(n)) O(log(n)) OK

asc and desc sorts have the same speed the slight measured difference is only due to CACHE as they both use the same memory space so which one is called in test first will be slower and second one benefits from the fact the memory is mapped in CACHE already (if not too large of coarse). btw this code can be further optimized by a bit...