Search code examples
javaalgorithmsortingbubble-sort

Why does Bubble Sort outer loop end at n-1?

I found this bubble sort (first sort I'm ever studying), I understand it almost fully but I'm stuck on one spot.

    public static int[] bubbleSort(int[] tempArray) { 
    int i, j, temp, n = tempArray.length; 
    boolean swapped; 
    for (i = 0; i < n - 1; i++) { 
        swapped = false; 
        for (j = 0; j < n - i - 1; j++) { 
            if (tempArray[j] > tempArray[j + 1]) { 
                temp = tempArray[j]; 
                tempArray[j] = tempArray[j + 1]; 
                tempArray[j + 1] = temp; 
                swapped = true; 
            } 
        } 
        if (swapped == false) 
            break; 
    }
    return tempArray; 
}

what is the point of "n - 1" in outer loop besides helping to make inner loop (n - i - 1) shorter? I tried removing the "n -1" and having count++ to work in the inner loop and the result was the same, so what is the reason for it then? Thanks!

Solution

  • It is because the largest element is already sorted in the first iteration.

    A picture is worth a thousand words

    enter image description here

    Image is from https://en.wikipedia.org/wiki/Bubble_sort

    Additional there is no need for the last element because bubble sort is all about swapping adjacent element and the last element doesn't have adjacent element.