Sorting an Array of int using BubbleSort

Solution 1:

You need two loops to implement the Bubble Sort .

Sample code :

public static void bubbleSort(int[] numArray) {

    int n = numArray.length;
    int temp = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < (n - i); j++) {

            if (numArray[j - 1] > numArray[j]) {
                temp = numArray[j - 1];
                numArray[j - 1] = numArray[j];
                numArray[j] = temp;
            }

        }
    }
}

Solution 2:

You're only making one pass through your array! Bubble sort requires you to keep looping until you find that you are no longer doing any swapping; hence the running time of O(n^2).

Try this:

public void sortArray(int[] x) {
    boolean swapped = true;
    while (swapped) {
       swapped = false;
       for(int i=1; i<x.length; i++) {
           int temp=0;
           if(x[i-1] > x[i]) {
               temp = x[i-1];
                x[i-1] = x[i];
                x[i] = temp;
                swapped = true;
            }
        }
    }
}

Once swapped == false at the end of a loop, you have made a whole pass without finding any instances where x[i-1] > x[i] and, hence, you know the array is sorted. Only then can you terminate the algorithm.

You can also replace the outer while loop with a for loop of n+1 iterations, which will guarantee that the array is in order; however, the while loop has the advantage of early termination in a better-than-worst-case scenario.