[java] Sorting an Array of int using BubbleSort

Why is my printed out Array not sorted in the below code?

public class BubbleSort {

   public void sortArray(int[] x) {//go through the array and sort from smallest to highest
      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;
         }
      }
   }

   public void printArray(int[] x) {
      for(int i=0; i<x.length; i++)
        System.out.print(x[i] + " ");
   }

   public static void main(String[] args) {
      // TestBubbleSort
      BubbleSort b = new BubbleSort();
      int[] num = {5,4,3,2,1};
      b.sortArray(num);
      b.printArray(num);   
   }
}

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.

Standard Bubble Sort implementation in Java:

//Time complexity: O(n^2)
public static int[] bubbleSort(int[] arr) {

    if (arr == null || arr.length <= 1) {
        return arr;
    }

    for (int i = 0; i < arr.length; i++) {
        for (int j = 1; j < arr.length - i; j++) {
            if (arr[j - 1] > arr[j]) {
                arr[j] = arr[j] + arr[j - 1];
                arr[j - 1] = arr[j] - arr[j - 1];
                arr[j] = arr[j] - arr[j - 1];
            }
        }
    }

    return arr;
}

Bubble sort algorithm is a simplest way of sorting array elements.Most of another algorithms are more efficient than bubble sort algorithm..Worst case and average case time complexity is (n^2).Let's consider how to implement bubble sort algorithm.

class buble_sort{
  public static void main(String a[]){

    int[] num={7,9,2,4,5,6,3};
    int i,j,tmp;

    for(i=0;i<num.length;i++){
        for(j=0;j<num.length-i;j++){
            if(j==(num.length-1)){
                break;
            }
            else{
                if(num[j]>num[j+1]){
                    tmp=num[j];
                    num[j]=num[j+1];
                    num[j+1]=tmp;
                }
            }
        }
    }

    for(i=0;i<num.length;i++){
        System.out.print(num[i]+"  ");
    }
}

}

Here is an example of bubbleSort, and Time Complexity is O(n).

 int[] bubbleSort(int[] numbers) {
        if(numbers == null || numbers.length == 1) {
            return numbers;
        }

        boolean isSorted = false;

        while(!isSorted) {
            isSorted = true;
            for(int i = 0; i < numbers.length - 1; i++) {
                if(numbers[i] > numbers[i + 1]) {
                    int hold = numbers[i + 1];
                    numbers[i + 1] = numbers[i];
                    numbers[i] = hold;
                    isSorted = false;
                }
            }
        }

        return numbers;
    }

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

public class Bubblesort{

  public static int arr[];

  public static void main(String args[]){

    System.out.println("Enter number of element you have in array for performing bubblesort");

    int numbofele = Integer.parseInt(args[0]);

    System.out.println("numer of element entered is"+ "\n" + numbofele);

    arr= new int[numbofele];

    System.out.println("Enter Elements of array");

    System.out.println("The given array is");


    for(int i=0,j=1;i<numbofele;i++,j++){

      arr[i]=Integer.parseInt(args[j]);

      System.out.println(arr[i]);

    }

    boolean swapped = false;

    System.out.println("The sorted array is");

    for(int k=0;k<numbofele-1;k++){


      for(int l=0;l+1<numbofele-k;l++){

        if(arr[l]>arr[l+1]){

          int temp = arr[l];
          arr[l]= arr[l+1];
          arr[l+1]=temp;
          swapped=true;

        } 

      }

         if(!swapped){

            for(int m=0;m<numbofele;m++){

       System.out.println(arr[m]);

    }

      return;

      }


    }

    for(int m=0;m<numbofele;m++){

       System.out.println(arr[m]);

    }


  }


}

This isn't the bubble sort algorithm, you need to repeat until you have nothing to swap :

public void sortArray(int[] x) {//go through the array and sort from smallest to highest
  for(;;) {
      boolean s = 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;
            s = true;
         }
      }
      if (!s) return;
  }
}

Here we go

static String arrayToString(int[] array) {
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < array.length; i++) {
      stringBuilder.append(array[i]).append(",");
    }
    return stringBuilder.deleteCharAt(stringBuilder.length()-1).toString();
  }

  public static void main(String... args){
    int[] unsorted = {9,2,1,4,0};
    System.out.println("Sorting an array of Length "+unsorted.length);
    enhancedBubbleSort(unsorted);
    //dumbBubbleSort(unsorted);
    //bubbleSort(unsorted);
    //enhancedBubbleSort(unsorted);
    //enhancedBubbleSortBetterStructured(unsorted);
    System.out.println("Sorted Array: "+arrayToString(unsorted));

  }

  // this is the dumbest BubbleSort
  static int[] dumbBubbleSort(int[] array){
    for (int i = 0; i<array.length-1 ; i++) {
      for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
          // Just swap
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
      }
      System.out.println("After "+(i+1)+" pass: "+arrayToString(array));
    }
    return array;
  }

  //this "-i" in array.length - 1-i brings some improvement.
  // Then for making our bestcase scenario better ( o(n) , we will introduce isswapped flag) that's enhanced bubble sort

  static int[] bubbleSort(int[] array){
    for (int i = 0; i<array.length-1 ; i++) {
      for (int j = 0; j < array.length - 1-i; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
      }
      System.out.println("After "+(i+1)+" pass: "+arrayToString(array));
    }
    return array;
  }

  static int[] enhancedBubbleSort(int[] array){
    int i=0;
    while (true) {
      boolean swapped = false;
      for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          swapped =true;
        }
      }
      i++;
      System.out.println("After "+(i)+" pass: "+arrayToString(array));
      if(!swapped){
        // Last iteration (of outer loop) didnot result in any swaps. so stopping here
        break;
      }
    }
    return array;
  }

  static int[] enhancedBubbleSortBetterStructured(int[] array){
    int i=0;
    boolean swapped = true;
    while (swapped) {
      swapped = false;
      for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          swapped = true;
        }
      }
      i++;
      System.out.println("After "+(i)+" pass: "+arrayToString(array));
    }
    return array;
  }

public class SortingArray {
public static void main(String[] args) {

int[] a={3,7,9,5,1,4,0,2,8,6};
int temp=0;

boolean isSwapped=true;


System.out.println(" before sorting the array: ");

for(int i=0;i<a.length;i++)
{
    System.out.print(a[i]);
}
System.out.println("");

do
{

isSwapped=false;

for(int i=0;i<a.length-1;i++)

{

    if(a[i]>a[i+1])

    {

        temp=a[i];

        a[i]=a[i+1];

        a[i+1]=temp;

    }



}


}while(isSwapped);


System.out.println("after sorting the array: ");

    for(int array:a)

    {

        System.out.print(array);


    }
  }
}

Really not getting the bubble sort, which can be called a sinking sort more appropriately since it's actually sinking the bigger/heavier to the bottom as the majority of the answers presented. One of the most typicals will be

private static void sortZero(Comparable[] arr) {
    boolean moreSinkingRequired = true;
    while (moreSinkingRequired) {
        moreSinkingRequired = false;
        for (int j = 0; j < arr.length - 1; ++j) {
            if (less(arr, j + 1, j)) { 
                exch(arr, j, j + 1);
                moreSinkingRequired = true;
            }
        }
    }
}

By the way, you have to traverse once more than actually required to stop earlier.

But as I see it bubbling as

private static void sortOne(Comparable[] arr) {
    for (int i = 0; i < arr.length - 1; ++i) {
        for (int j = arr.length - 1; j > i; --j) { // start from the bottom
            if (less(arr, j, j - 1)) {
                exch(arr, j - 1, j);
            }
        }
    }
}

You have to know this method is actually better since it's tracking the end point for comparison by j > i with [0, i-1] already sorted.

We also can add earlier termination but it then becomes verbose as

private static void sortTwo(Comparable[] arr) {
    boolean moreBubbleRequired = true;
    for (int i = 0; i < arr.length - 1 && moreBubbleRequired; ++i) {
        moreBubbleRequired = false;
        for (int j = arr.length - 1; j > i; --j) {
            if (less(arr, j, j - 1)) {
                exch(arr, j - 1, j);
                moreBubbleRequired = true;
            }
        }
    }
}

The utils used to make the process terse are

public static boolean less(Comparable[] arr, int i, int j) {
    return less(arr[i], arr[j]);
}

public static boolean less(Comparable a, Comparable b) {
    return a.compareTo(b) < 0;
}

public static void exch(Comparable[] arr, int i, int j) {
    Comparable t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

Your sort logic is wrong. This is the pseudo-code for bubble sort:

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    ? invariant: a[1..i] in final position
    break if not swapped
end

See this sorting web site for good tutorial on all the various sorting methods.

I use this method for bubble sorting

public static int[] bubbleSort (int[] a) {
    int n = a.length;
    int j = 0;
    boolean swap = true;
    while (swap) {
        swap = false;
        for (int j = 1; j < n; j++) {
            if (a[j-1] > a[j]) {
                j = a[j-1];
                a[j-1] = a[j];
                a[j] = j;
                swap = true;
            }
        }
        n = n - 1;
    }
    return a;
}//end bubbleSort

public class BubbleSort {

    public void sorter(int[] arr, int x, int y){

            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;

    }

    public void sorter1(String[] arr, int x, int y){

        String temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;

    }

    public void sertedArr(int[] a, String[] b){
        for(int j = 0; j < a.length - 1; j++){
            for(int i = 0; i < a.length - 1; i++){
                if(a[i] > a[i + 1]){
                    sorter(a, i, i + 1);
                    sorter1(b, i, i + 1);
                }
            }
        }
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i]);
        }
        System.out.println();
        for(int i = 0; i < b.length; i++){
            System.out.print(b[i]);
        }
        // 
    }
    public static void main(String[] args){
        int[] array = {3, 7, 4, 9, 5, 6};
        String[] name = {"t", "a", "b", "m", "2", "3"};
        BubbleSort bso = new BubbleSort();
            bso.sertedArr(array, name);
    }
}

java code

public void bubbleSort(int[] arr){   

    boolean isSwapped = true;

    for(int i = arr.length - 1; isSwapped; i--){

        isSwapped = false;

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

            if(arr[j] > arr[j+1]}{
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                isSwapped = true;
            }
        }

    }

}

Bubble sort nested loops should be written like this:

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

for(int i=0; i < n; i++){
   for(int j=1; j < (n-i); j++){                        
       if(intArray[j-1] > intArray[j]){
            //swap the elements!
            temp = intArray[j-1];
            intArray[j-1] = intArray[j];
            intArray[j] = temp;
       }                    
   }
}