Optimizing Bubble Sort by skipping elements in the inner loop

Question

Please help me to understand the logic behind these 2 methods of optimizing bubble sort:

Method 1

public static void MyBubbleSort()
{

    for (int i=0; i<list.length; i++)
    {
        boolean is_sorted = true;
        for (int j=0; j<list.length-1; j++)
        {
            if (list[j]>list[j+1])

            {

                    int a = list[j];
                    list[j]=list[j+1];
                    list[j+1]=a;
                    is_sorted = false;
                System.out.println ("Ascending order:"+Arrays.toString(list))} 

Method 2

Here, I don't get what the -i is doing in the inner loop.

 public static void MyBubbleSort()
{

    for (int i=0; i<list.length; i++)
    {

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

            {

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

                System.out.println ("Ascending order:"+Arrays.toString(list));

Answer 1

In Bubble Sort, At the end of each iteration, the Largest remaining element gets to its final position. For example , in the following array.

6 2 5 3 8 7 1

After the first iteration, 8 will be the last element in the array, which is its final position.

At the end of second iteration, 7 will be the second last element in the array, which is its final position.

So, after each iteration, we dont need to compare the elements that have reached their final position.

So, After first iteration, we only need to compare length - 1 (here i = 1) elements. At the end of second iteration, we only need to compare length - 2 (i = 2) elements.

Please have a look at the animation at https://en.wikipedia.org/wiki/Bubble_sort link. This will help in more clarity.

Answer 2

Bubble sort works by comparing adjacent elements moving up the array. In a trivial example, [3, 2, 1], the first comparison in the inner (j-index) loop is between 3 and 2; 3 "wins" and swaps with 2. Then 3 and 1 are compared, and 3 "wins" again and is in the last index of the array, which is then [2, 1, 3] after this first pass.

Effectively, the purpose of the inner (j-index) loop is to move the biggest element to the back of the array. The biggest element will "win" all of the comparisons along the way.

Therefore, after one run of the outer loop, the last element is definitely sorted, is the maximum element, and is in its final place and never needs to be re-inspected. After two runs of the outer loop, the last two elements are in their final places and never need to be re-inspected. Following this logic, we can stop the inner loop at end - i - 1 to save pointless comparisons.

If you're not convinced, print the entire array after each inner loop run using a toy example:

import static java.lang.System.out;

class Main {
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }

            print(arr, i);
        }
    }

    public static void print(int[] arr, int p) {
        int i = 0;
        out.print(
            "after " + (p + 1) + (p + 1 == 1 ? 
            " pass:   " : " passes: ") + "[ "
        );

        while (i < arr.length - 1 - p) {
            out.print(arr[i++] + ", ");
        }

        out.print("(");

        while (i < arr.length - 1) {
            out.print(arr[i++] + ", ");
        }

        out.println(arr[i] + ") ]");
    }

    public static void main(String[] args) {
        int[] arr = {9,5,7,1,4,7,2};
        bubbleSort(arr);
    }
}

Output

after 1 pass:   [ 5, 7, 1, 4, 7, 2, (9) ]
after 2 passes: [ 5, 1, 4, 7, 2, (7, 9) ]
after 3 passes: [ 1, 4, 5, 2, (7, 7, 9) ]
after 4 passes: [ 1, 4, 2, (5, 7, 7, 9) ]
after 5 passes: [ 1, 2, (4, 5, 7, 7, 9) ]
after 6 passes: [ 1, (2, 4, 5, 7, 7, 9) ]
after 7 passes: [ (1, 2, 4, 5, 7, 7, 9) ]

Elements that are in their final position and never need to be touched are delimited by parenthesis. You can see they stay put all the way down the sort. Play around with the code a bit if you're curious. Try sorting in reverse and with various inputs.

Incidentally, there are additional optimizations. For example, notice in the above example that after 5 passes, the array is totally sorted. Adding a boolean flag to determine if a swap was performed in a given pass allows you to bail out early and skip a few final iterations.

None of these improvements help with the O(n²) time complexity, though. The time spent sorting grows quadratically in proportion to the input size on worst-case inputs.