I have been learning data structure and algorithm in Java and I don’t know how this line of code work in this code. At the second line of code , there is nested looping and I still don’t understand how that line works. How does array.length – i – 1 work in my code? And the code is about bubble sorting.
Following is the code snippet.
for(int i = 0; i < array.length - 1 ; i++) {
for(int j = 0 ; j < array.length - i - 1 ; j++) {
if(array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
>Solution :
This is a simple swap (bubble) sort algorithm. For a list of length N to be sorted, it walks across the list N - 1 times, swapping entries to move larger values towards the end of the list and smaller values towards the beginning. After the first pass, the last item in the list is guaranteed to be in the right location. So for the second pass, the inner loop doesn’t have to consider the last possible swap. After the second pass, the last two items are guaranteed to be in the right place, so the inner loop can now ignore the last two swaps. After the third pass, the last three items are guaranteed to be in the right place. And so on and so on.
The arrays.length - i - 1 expression is accounting for the fact that with each pass over the list, there is one less pair of items that has to be considered, per the explanation above. Due to this expression, on the last pass over the list (the last iteration of the outer loop), only the first and second items in the list can possibly be out of order, so only a single comparison and possible swap is done in the last iteration.