Java Bubble Sort Returns Only Partially Sorted

Question

I'm new to Java, so have been trying to translate some old JS exercises into Java.

Here's a bubble sort (I know, I know...) that's not working:

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

int nums [] = {5, 4, 6, 3, 12, 1};


Boolean swap = true;
while(swap){
    swap = false;
    for(int i = 1; i<nums.length ; i++){
        if (nums[i - 1] > nums[i]){
            int t = nums[i-1];
            nums[i-1] = nums[i];
            nums[i] = t;
            swap = true;
        }else{
            swap = false;
        }
    }
}

System.out.print("Sorted: ");
for(int j=0 ; j<nums.length ; j++)
System.out.print(nums[j] + " ");
}
}

It returns 4, 3, 5, 1, 6, 12... So a few swaps are taking place, but something is making it end early.

Can anyone spot my issue?

Answer 1

Just remove the else block in your code (as in the code sample below). You have to make another swap as soon as one thing is not ordered.

In your code, you only make another swap if the last items are in the wrong order. If the end of your array is ordered too soon, your sort ends too soon too.

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

        int nums [] = {5, 4, 6, 3, 12, 1};

        Boolean swap = true;
        while(swap){
            swap = false;
            for(int i = 1; i<nums.length ; i++){
                if (nums[i - 1] > nums[i]){
                    int t = nums[i-1];
                    nums[i-1] = nums[i];
                    nums[i] = t;
                    swap = true;
                }/* else{
                    swap = false;
                }*/
            }
        }

        System.out.print("Sorted: ");
        for(int j=0 ; j<nums.length ; j++)
            System.out.print(nums[j] + " ");
    }
}

Answer 2

Yes. Don't reset swap to false with the else; and prefer boolean to Boolean. Like,

boolean swap = true;
while (swap) {
    swap = false;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i - 1] > nums[i]) {
            int t = nums[i - 1];
            nums[i - 1] = nums[i];
            nums[i] = t;
            swap = true;
        }
    }
}

Outputs

Sorted: 1 3 4 5 6 12 

With no other changes. This could be refined with a few lambdas and extracting the swap method would also help. Something like,

private static void swap(int[] arr, int i, int j) {
    if (arr[i] > arr[j]) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

public static void main(String args[]) {
    int nums[] = { 5, 4, 6, 3, 12, 1 };
    IntPredicate ip = i -> nums[i - 1] > nums[i];
    while (IntStream.range(1, nums.length).anyMatch(ip)) {
        IntStream.range(1, nums.length).forEach(i -> swap(nums, i - 1, i));
    }
    System.out.print("Sorted: " + IntStream.of(nums)
            .mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}

Answer 3

As many others have already said, setting swap to false in your comparison step is incorrect. Your code will terminate prematurely if the final comparison in the loop does not result in a swap.

Since you are asking about bubbleSort, what you have implemented is not actually bubble sort. classic BubbleSort uses a pair of nested for loops. The outer loop finds the largest number in the list and ensures it bubbles up to the top position in the array starting at index n-1, then n-2, etc.

The inner loop scans all elements from index 0 to up to that position set by the outer loop, and pairwise compares the elements, and swaps them if they are out of order.

Here is classic bubbleSort:

class BubbleSort{

     /**
      * Swaps to elements in array data at index1 and index2
      *
      * @param data the array whose elements should be swapped
      * @param index1 index of first element to be swapped
      * @param index2 index of second elememt to be swapped with the first
      *
      */
     private static <T extends Comparable<T>>  void swap(T[] data, int index1, int index2)
        {
          T temp       = data[index1];
          data[index1] = data[index2];
          data[index2] = temp;
        }       

    /**
     * Sorts the specified array of objects using a bubble sort algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>> void bubbleSort(T[] data)
    {
        int position, scan;

        for (position =  data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap(data, scan, scan + 1);
            }
        }
    }


public static void main(String args[]){
   Integer nums [] = {5, 4, 6, 3, 12, 1};

   bubbleSort(nums);

   System.out.print("Sorted: ");
   for(int j=0 ; j<nums.length ; j++)
      System.out.print(nums[j] + " ");
   System.out.println("");
  }
}

Answer 4

static void sort(int[] a) {
        for (int i = a.length - 2; i >= 0; i--) {
            boolean flag = true;
            for (int j = 0; j <= i; j++) {
                if (a[j] > a[j + 1]) {
                    flag = false;
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
            if (flag)
                break;
        }
    }

Answer 5

remove the else block and it will work

    Boolean swap = true;
    while(swap){
        swap = false;
        for(int i = 1; i<nums.length ; i++){
            if (nums[i - 1] > nums[i]){
                int t = nums[i-1];
                nums[i-1] = nums[i];
                nums[i] = t;
                swap = true;
            }
        }
    }

this else block make it wrong because if your last check in for dont need swap, it will end the outer while loop

Answer 6

When your first inner loop ends without a swap, that swap marker boolean is false, and the outer loop stops.

That is all there is to this.