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

user_12968527 0
Viewed 432

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!

bubble-sort sorting algorithm java
2 Answers

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.

user_65831340

It is because bubble sorting works on swapping of adjacent element. If outer loop goes till n then in the inner loop you cannot pick another element. 

temp = tempArray[j]; 
tempArray[j] = tempArray[j + 1]; 
tempArray[j + 1] = temp;

This is because the size of array is till n and inner loop swap between j and j+1. Feel free to ask further doubts.

user_105018480
Related