Bubble Sort Java different outputs

Question

I have been confronting with a very confusing situation, I wrote this BubbleSort program and it ran just fine. with the correct output:

public class BubbleSortInput {

private static void Sorting(int[] intArray)
{
    int i, temp=0;
    int n = intArray.length;

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

public static void main(String[] args) {

    int array[] = {1,5,65,34,76,234};

    Sorting(array);
    for(int k = 0; k < array.length; k++)
    {
        System.out.println(array[k]);
    }
}
}

However, I tried to write basically the same code, in the main method, in another class:

class BubbleSort {
public static void main(String[] args) {
   int numbers[] = {12,43,65,12,65,92,32,54};
   int i,temp=0;

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

    for(i=0;i<numbers.length;i++)
    {
        System.out.println(numbers[i]);
    }
}
}

The output I get on the second file is completely wrong, even though I used almost the same code, Can someone explain this please?

Output: 

12
43
12
12
65
32
32
54

Did you try debugging the code? See [What is a debugger and how can it help me diagnose problems?](http://stackoverflow.com/q/25385173/5221149) — Andreas, Aug 30 '16 at 03:22
I don't see how either of them can work, given that `intArray[i] = intArray[i+1]` and `numbers[i] = numbers[i+1]` are both assigning the wrong way. — Andreas, Aug 30 '16 at 03:23
Possible duplicate of [Java Bubble Sort wrong output](http://stackoverflow.com/questions/18877036/java-bubble-sort-wrong-output) — karan, Aug 30 '16 at 05:00

score 0 · Answer 1 · answered Aug 30 '16 at 03:23

I don't think your bubble sorting code is correct. Here is your loop:

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

Note that you never use the variable j. So all it does is loop through the array and then swap the two elements if the first one is larger than the second one. You should take a look at the Bubble sort algorithm again and re-write your code.

Also notice how `intArray[i] = intArray[i+1]` is assigning the wrong way for a swap operation. — Andreas, Aug 30 '16 at 03:24

score 0 · Accepted Answer · answered Aug 30 '16 at 03:51

As others pointed out, you should take a look at the bubble sorting algorithm. And just a reminder, run many test cases before stating that your original piece of code works fine. Just to be clear, the first program also gives a wrong output. The output you may have gotten for your input set may be true, but that was a bit sorted to begin with. Try the input set you used in the second program for your first code and identify the errors.And also, take a look at the swapping code inside your for loops.

                temp = intArray[i+1];
                intArray[i] = intArray[i+1];
                intArray[i] = temp;

You are assigning the value at [i+1] position to temp. And you are again assigning the value at [i+1] to the location i. So the value at the location [i] was lost in the process. Now value at location [i] and [i+1] are same. So work on that as well.

That aside. In Bubble sort, sorting works by swapping adjacent elements. So by the end of the first pass(ascending order sorting), the largest element in the array will be at the end. This process goes on until, all the elements are sorted.

Example:
First Pass:
( 6 1 3 2 9 ) –> ( 1 6 3 2 9 ), Here, algorithm compares the first two elements, and swaps since 6 > 1.
( 1 6 3 2 9 ) –>  ( 1 3 6 2 9 ), Swap since 6 > 3
( 1 3 6 2 9 ) –>  ( 1 3 2 6 9 ), Swap since 6 > 2
( 1 3 2 6 9 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (9 > 6), algorithm does not swap them.
Second Pass:
( 1 3 2 6 9 ) –> ( 1 3 2 6 9 )
( 1 3 2 6 9 ) –> ( 1 3 4 6 9 ), Swap since 3 > 2
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )
( 1 2 3 5 9) –>  (1 2 3 5 9 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 3 5 9 ) –> (1 2 3 5 9 )
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )

@rookie101 If you found the answer appropriate and right, please click on the 'tick' symbol next to my post. Cheers — Govind Madhu, Aug 31 '16 at 03:23

score 0 · Answer 3 · answered Aug 30 '16 at 04:16

The sorting logic you are using is incorrect.

Bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order (not in ascending order). By the end of the first pass(ascending order sorting), the largest element in the array will be at the last index. By the end of the second pass(ascending order sorting), the second largest element in the array will be at the second last index and so on.....

Visit http://visualgo.net/sorting for better understanding.

So, in your code you should compare the items with the 2nd initialization (variable j in your case). After modification it should look like:

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

Thank you, this really helped me to understand the whole process — rookie101, Aug 30 '16 at 13:38

Bubble Sort Java different outputs

3 Answers3