Can somebody explain the last method in this code?

Question

I'm a beginner programmer and I don't understand the last method (mysort) in this code. It's actually an example for bubble sort.

import java.util.*;
public class Sort
{
public static void main(String[] args)
{
    int[] a = {22, 55, 44, 11, 33};
    disp(a);
    mysort(a);
    disp(a);
}
public static void disp(int[] x)
{
    for(int e : x)
    {
        System.out.print(e + "\t");
    }
    System.out.println();
}

public static void mysort(int[] a)
{
    int l = a.length;
    for(int i = 0; i < l - 1; i++)
    {
        for(int j = 0; j < l - 1 - i; j++)
        {
            if(a[j + 1] < a[j])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}
}

Answer 1

Let's break down each piece of the method. The first part of the code to understand is the inner most block:

int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;

If we were to run the above statements on the array {1,2,3,4,5}, with j=2, We would have:

int temp = a[2] --> 3;
a[2] = a[2+1] --> a = {1,2,4,4,5};
a[2+1] = temp --> a = {1,2,4,3,5};

We now see that these three lines swap the elements of a[j] and a[j+1].

Now we look at the for loops. The inner loop: for(int j = 0; j < l - 1 - i; j++) is looping from the start of the array up to l-1-i. At each index, it asks if(a[j+1] < a[j]), meaning "is the element at index j+1 smaller than the element at index j", or more concretely, "Should the elements at j+1 and j be swapped?"

The outer loop is simply running over the whole array with index variable i. Taking the two loops together, we see that j will first loop over the whole array without the last index, then the whole array without the last two indices, then without the last three, etc. For example, if l = 10, j will take on the values:

0 1 2 3 4 5 6 7 8 //i = 0, l - 1 - i = 9
0 1 2 3 4 5 6 7   //i = 1, l - 1 - i = 8
0 1 2 3 4 5 6     //i = 2, l - 1 - i = 7
...
0

So the two for loops together are running over some fraction of the array l times, making swaps.

The reason for the loops being formed this way is that after each iteration of j=0...l-1-i, the last element is known to be in its sorted location, so we don't have to check it again. That justification and more here: http://en.wikipedia.org/wiki/Bubble_sort