Search code examples
javasortingbubble-sort

Improving Bubble sort by making it notice where the last swap took place

How do I improve this code to make it Instead of reducing i by one each time, set it to where the last swap took place (the lower position). If no swaps took place, i should get set to zero, which will end the loop

public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    for (int i = a.length - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

This is my attempt at it.

 public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    boolean swap = false;
    for (int i = a.length - 1; i > 0;) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                swap = true;
            }
            if (swap) {
                i = j;
            } else {
                i = 0;
            }
        }
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

The code that prints my output is the following:

 bubbleSort(check);
    System.out.printf("%1$-19s %2$10d %3$19d %4$19d", "Bubble", numComp, numAsgn, numComp + numAsgn);
    System.out.println();
    resetCounts(); //resets numComp and numAsgn to 0

Input example: [2, 5, 5, 3, 1, 3, 4, 4, 3, 4]

Output:

enter image description here

Solution

  • Probably something like this:

    public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    int lastSwap = a.length - 1, i;
    for (i = lastSwap; i > 0;) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                lastSwap = j;
            }
        }
        if(i == lastSwap) {
            //sorted
            break;
        }
        i = lastSwap;
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

    This should give you some improvement, but the worst case remains the same, as expected.