Created almost working sort algorithm but I don't understand the second for-loop

Question

This is what I coded myself and I understand everything what is done here:

import java.util.Arrays;
public class Decision{
    public static void main (String[]args){
        int[] myArray = {1,8,3,0,2};


        for(int i=0; i<myArray.length-1; i++){
        if(myArray[i]<myArray[i+1]){

        }
        else{
            int temp=myArray[i];
            myArray[i]=myArray[i+1];
            myArray[i+1]=temp;
        }

        System.out.println(Arrays.toString(myArray));
        }   
    }
}

Output: [1, 3, 0, 2, 8]

So we first check if the first value in the array is smaller than the next one. If yes, then don't do anything. If not, then swap both.

The problem with this sort algorithm is that it won't swap as example the first value with the third one, or the second with the fifth, etc.

I realized this sort works perfectly if we add a second for-loop that repeats the for-loop in my code:

for(int n=myArray.length; n>1; n=n-1){
...
}

I also realized this kind of sort is called bubble sort, but please explain me the important role of this for-loop, I'm sad I cannot understand what it does at all? : /

Answer 1

In all honesty I'm a bit confused about your question. Normally I'd recommend adding diagnostics printouts, but you already have one. As you can see, doing only one pass can at most swap an item with the one next to it. There's no way you can fully sort the array this way, because once you process one element at [i], your algorithm of course can't move that element anywhere else. So if it's not in its final correct position after that one pass, it'll never get there. In particular, a given element can only be moved to the left at most 1 position per pass. The worst case of this is if the input is sorted in decreasing order before going in.

When you add an outer loop doing multiple passes, it sorts the array a little bit more each time, until finally it's sorted. Doing myArray.length - 1 passes guarantees that even the worst-case elements get a chance to be "moved" through the entire array to their correct position, because in the worst case input it guarantees that you'll be able to move an element left through the entire array (in an array of length n it takes n-1 moves to get the element in the last position into the first position -- if this doesn't click, draw it on paper and count).

I mean, there is an important skill missing from your toolset that you really ought to learn, which is that you need to get used to visualizing what your code does. There are a few ways to do this:

1. Research the algorithm you are implementing. The linked wiki article on bubble sort pretty clearly explains the algorithm in the step-by-step section.
2. With some experience it will make sense in your head.
3. Work things out on paper.
4. Trace through things line-by-line in your debugger.
5. Add temporary trace print-outs to your programs.
6. And of course, sometimes experimenting with algorithms by breaking them and observing the changes.

You went with #5 and #6, you just need to learn how to interpret the information. Here is a working version of your sort, for example (ignoring other potential code improvements, I am certain other answers here will help you along those line) with one extra print added to separate the passes in the output:

public static void main (String[]args){
    int[] myArray = {1,8,3,0,2};

    for(int n=myArray.length; n>1; n=n-1){
        System.out.println("Outer loop: " + n);
        for(int i=0; i<myArray.length-1; i++){
            if(myArray[i]<myArray[i+1]){
            }
            else{
                int temp=myArray[i];
                myArray[i]=myArray[i+1];
                myArray[i+1]=temp;
            }
            System.out.println(Arrays.toString(myArray));
        }   
    }
}

This outputs:

Outer loop: 5
[1, 8, 3, 0, 2]
[1, 3, 8, 0, 2]
[1, 3, 0, 8, 2]
[1, 3, 0, 2, 8]
Outer loop: 4
[1, 3, 0, 2, 8]
[1, 0, 3, 2, 8]
[1, 0, 2, 3, 8]
[1, 0, 2, 3, 8]
Outer loop: 3
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
Outer loop: 2
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]

As you can see, after the first pass it's not fully sorted. The second pass is a bit closer. The third pass completes it in this case. It's the 0 that's holding things up in this case: The 0 has to move left 3 positions, and so you must complete at least 3 passes.

For an even clearer picture try that ideone example with the worst case input of [8, 3, 2, 1, 0].

Answer 2

Instead of adding the 2nd loop you could also say

boolean change = true;
while (change) {
   change = false;
   ...
     if (a[i] > a[i + 1]) { // write it like this and you don't need an else
       change = true;
       // swap
     }
   ...
}

Both work, because the maximum number of passes needed to sort the array is n - 1. For the worst case, an array sorted descending instead of ascending, the elements will wander to the end like water bubbles to the top of the water. On the first iteration the first element will end up in the last position, on the 2nd iteration the originally 2nd element (now first) will travel up to the 2nd last position and so on. So you can see that you need only n-1 iterations, because on the (n-1)th iteration the originally 2nd last element (now the first) will end up in 2nd position and the originally last element (now the first) is already sorted correctly.

You can also notice, that on each iteration (at least) one more element at the end of the array ends up in its correct position, so you can decrease the max for the inner loop on each iteration.

Answer 3

Assume the worst case for this algorithm, an array sorted in reverse order and see what happens with one loop

4 3 2 1 0    original array
3 4 2 1 0    after one swap
3 2 4 1 0    after two swaps
3 2 1 4 0    after three swaps
3 2 1 0 4    after the complete loop

You see that only the largest element is now in the right place, all the rest is still in reverse order. After a second pass the second largest element will be in the correct place as well and so on.

Note that the passes after the first do not have to go over the full array (but it does not hurt) because more and more elements will already have reached their final position.